This unit is an introduction to Computational Geometry, the art of solving complex geometrical problems with computer programs. Although it is not currently a mandatory topic to study for IOI, it is good to have some basics since it has interesting algorithms and is an increasingly important topic in ACM-ICPC (if you plan to continue algorithmics in university).
The theory covered is:
- Basics of 2D geometry
- Useful formulas
- Handling floiting point errors
- Polygons, area, convexity, check if inside
- Convex hull
- Secondary-school synthetic geometry (years 1 and 2)
- Unit 1: Complexity
- Unit 3: Sorting (just using a sort function with comparator)
- UVa 634 - Polygon (check if inside)
- UVa 10060 - A Hole to Catch a Man (areas)
- UVa 478 - Points in Figures: Rectangles, Circles, and Triangles (check if inside, variants)
- UVa 681 - Convex Hull Finding (I'll let you guess)
- UVa 920 - Sunny Mountains
- UVa 1111 - Trash Removal
- UVa 588 - Video Surveillance
- UVa 109 - SCUD Busters (convex hull, area)