Seminář 11 (29.11.) Geometrie

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

courses/a4b36acm2/2012_zs/seminar_b_2911.txt · Last modified: 2018/02/21 22:30 (external edit)