Hide

Problem M
Forest Highway

/problems/forest/file/statement/en/img-0001.jpg
The Slovak Government is building a highway from Bratislava to Košice. The highway will pass through a forest where a lot of animals live. Frog Gizela, the queen of the animals, wants to calculate the impact of the highway on their lives. Since the highway will be noisy, animals don’t want to live within distance $d$ from the highway. Gizela wants to know how large the inhabitable area will be. If the total inhabitable area of the forest is too small, Gizela will have to find a new forest for her kingdom.

Task

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.

\includegraphics[width=0.44\textwidth ]{polygon}
Figure 1: Drawing of the sample input

Input

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

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

Please log in to submit a solution to this problem

Log in