You are given a description of the forest and the highway. The forest is a simple polygon, i.e. its sides do not cross, and the highway can be considered a straight line of width zero. You are also given $d$, the safe distance from the highway. Calculate the size of the inhabitable area of the forest.
The first line of the input contains one integer $N$ $(3\leq N\leq 250\, 000)$ denoting the number of vertices of the polygon. $N$ lines follow with two floating point numbers $x_ i$ and $y_ i$, denoting that the $i$-th point of the polygon is $(x_ i, y_ i)$.
Next line contains 4 floating point numbers $x_ a, y_ a, x_ b, y_ b$, denoting that the highway passes through points $(x_ a, y_ a)$ and $(x_ b, y_ b)$. The last line of the input contains one positive floating point number $d$, the safe distance from the highway.
All floating point numbers will be at most $100\, 000$ in absolute value and will have at most 4 digits after the decimal point.
Output one line with one number – the size of the inhabitable area of the forest. Results with relative or absolute error $10^{-7}$ will be considered correct.
Sample Input 1 | Sample Output 1 |
---|---|
7 0.0 0.0 2.0 4.0 4.0 0.0 5.0 5.0 1.0 6.0 1.0 4.0 -1.0 3.0 -2.0 4.0 6.0 1.0 0.6 |
13.082798910 |