=== 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í  [[http://en.wikipedia.org/wiki/Convex_hull|konvexní obálky]], [[http://en.wikipedia.org/wiki/Voronoi_Diagram|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** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=861|920 - Sunny Mountains]]\\

**b2** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=417|476 - Points in Figures: Rectangles]]\\

**b3** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=394|453 - Intersecting Circles]]\\

**b4** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695|11648 - Divide The Land]]\\

**b5** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=57|121 - Pipe Fitters]]\\

**b6** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41|105 - The Skyline Problem]]\\


----------
**Něco navíc** \\

**b7**  [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1076|10135 - Herding Frosh]] \\

**b8**  [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=622|681 - Convex Hull Finding]]\\