Search
Menší část geometrických úloh využívá základních algoritmů výpočetní geometrie, jako jsou např. hledání konvexní obálky, Voroného diagramu apod. Protože to jsou spíše specializované postupy, někdy s delším kódem, tíhne většina autorů k úlohám, které vyžadují hlavně všeobecný geometrický postřeh a přehled o vlastnostech objektů v rovině (prostoru) a případně trochu elementární analytické geometrie vhodné pro výpočet. Doporučujeme osvěžit si například některé z následujících pojmů a vztahů: Rovnice přímky, kružnice. Vzdálenost dvou bodů. Vzdálenost bodu od přímky, od úsečky. Plocha trojúhelníka jako z.v/2, jako Heronův vzorec, jako vektorový součin, polovina lichoběžníka (determinant). Průnik dvou přímek. Průnik dvou úseček. Průnik dvou kružnic. Průnik úsečky a přímky. Zamyslete se, jak váš kód odpoví na otázky: Leží bod uvnitř kružnice? Leží bod uvnitř trojúhelníku? Leží bod uvnitř konvexního mnohoúhelníku? Leží bod uvnitř nekonvexního mnohoúhelníku? Protínají se dva trojúhelníky? Atd atd. Geometrické úlohy jsou rozmanité a ani pro jednoduché z nich neexistuje žádný všeobecný postup na jejich řešení. Buďte připraveni, že leckdy budete muset provést krátký nebo delší výpočet na papíře, kdy vám programovací zkušenosti pomohou jen málo.
Příklady k rozmyšlení
b1 920 - Sunny Mountains
b2 476 - Points in Figures: Rectangles
b3 453 - Intersecting Circles
b4 11648 - Divide The Land
b5 121 - Pipe Fitters
b6 105 - The Skyline Problem
Něco navíc
b7 10135 - Herding Frosh
b8 681 - Convex Hull Finding