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í
b2 476 - Points in Figures: Rectangles
Něco navíc