UVA 10084: Hotter Colder

Created at 2016-06-27T04:42:08.000Z
Problem Definition: https://uva.onlinejudge.org/external/100/10084.pdf

Techniques:

- Lines intersection
- Polygon area calculation

# Rough Sketch

- Calculate all crossing points from half plains
- From those crossing points, select a point if it is included in all half plains
- After this selection, points already form convex

- calculate convex area by the same approach I used here: http://wp.hiogawa.net/2016/04/10/uva-10065-useless-tile-picker/¨B¨K5K¨B

# References

- https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
- http://www-ma2.upc.edu/vera/DAG-MAMME/IntersectingHalfplanes.pdf¨B¨K6K¨B
- Bentley–Ottmann algorithm
- https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
- http://www.bowdoin.edu/~ltoma/teaching/cs350/spring04/Handouts/bentley-ottmann.pdf
- calculate crossing points from given line segments in $O((n + k)\log(n))$ where
`n`

is a number of line segments and`k`

is a number of crossing points. naively it's $O(n^2)$. - (I didn't implement this algorithm)