Naloga z vrvjo

Vrv je na hlode pripeta z žeblji. Jaz moram ugotoviti, na katere hlode se bo vrv pripela (tako kot na sliki). Iz levega konca mi je uspelo priti do sredine (če je višina drugega hloda - višina prvega > višina tretjega - višina drugega, potem je drugi hlod pravi. In potem gremo po istem principu naprej - če je višina tretjega hloda - višina drugega > višina četrtega - višina tretjega, potem je tretji pravi. itd). Kako pa bi šel naprej od tistega najvišjega proti zadnjemu na desni, pa nimam pojma. Sem probaval že ogromno for, pa mi ne rata. Prosim če ima kdo pametno idejo, naj jo napiše.

V bistvu iščeš konveksno lupino. Vrhe debel si lahko predstavljaš kot posamezne točke ali pa recimo kot žebljičke v risalni tabli. Če čez te žebljičke napneš elastiko, tako da bodo znotraj nje zajeti vsi žebljički, boš dobil konveksno lupino. Žebljički, okoli katerih bo napeta elastika so člani konveksne lupine oz. v tvojem primeru bodo to debla, preko katerih gre trak. Ta debla (točke, žebljičke), ki so člani konveksne lupine lahko najdeš z večimi algoritmi. Nekaj, ki se jih jaz spomin so npr. metoda s preiskovalno premico, inkrementalna metoda, Jarvishev obhod in še nekaj bi se jih našlo.