Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

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/a4b36acm1/2012_zs/seminar_b_2911.txt · Last modified: 2018/10/03 03:51 (external edit)