Problem A
Art Appreciation

Brandon Greg Jr. is an art enthusiast who covered the entirety of the walls of his room with works of art. Brandon’s room is in the shape of a simple polygon (simple means that the polygon does not intersect itself). If Brandon is at point $X$, then he can see all points $Y$ such that the line segment $XY$ (excluding point $Y$) does not intersect any walls. Since Brandon’s happiness is proportional to the amount of art he can see by turning his head, he wants to know the area of the set of points from where he could see all of the walls of his room (and thus see his entire art collection). You may assume that Brandon has a very flexible neck.


The first line of input contains a single integer $n$ ($3\le n\le 2\cdot 10^5$), representing the number of vertices of Brandon’s room.

Each of the next $n$ lines of input contains two space-separated real numbers $x_ i$ and $y_ i$ ($|x_ i|, |y_ i| \le 10^5$), representing the cartesian coordinates of the $i$-th vertex of Brandon’s room. The coordinates have at most two digits after the decimal place. It is guaranteed that the polygon is simple. The vertices may be given in clockwise or counterclockwise order.


Output the area of the set of points from where Brandon could see all of the walls of his room. The output will be considered correct if the absolute or relative error is within $10^{-4}$ of the answer (if $a$ is the output and $b$ is the answer, then $a$ will be considered correct if $\frac{|a-b|}{\max \{ 1,b\} } \le 10^{-4}$.

Sample Input 1 Sample Output 1
2 0
1 1
0 2
-2 0
0 -2
Sample Input 2 Sample Output 2
0.2 0.00
0 -0.2
0.0 0
-0.2 0
0 0.20
Sample Input 3 Sample Output 3
0 0
5 0
2 1
5 5
0 5
3 4

Please log in to submit a solution to this problem

Log in