Downsizing

문제

Renowned nuclear physicist Adam Szmasczer has found a solution to global overpopulation and scarce resources: shrink everything! More precisely, he has found a way to teleport regions of space (both bounded and unbounded) to a bounded set of points inside a finite spherical cell. He explains his process as follows (from here on, we will work only in two dimensions for simplicity).

Assume a circular cell of radius $rr$ is centered at a point $OO$. Let $PP$ be any point not in the interior of the cell, and suppose the line $\overline{OP}\backslash overline\{OP\}$ intersects the cell's boundary at the point $BB$. Then point $PP$ is teleported to a point $P^{\mathrm{\prime }}P\text{'}$ lying on this line, where $\text{length}(\overline{OP})\cdot \text{length}(\overline{O{P}^{\mathrm{\prime }}})=r^2\backslash text\{length\}(\backslash overline\{OP\})\backslash cdot\backslash text\{length\}(\backslash overline\{OP\text{'}\})\; =\; r^2$. (Points along the cell boundary are teleported to themselves.) Figure D.1 shows how a pentagonal "house" is teleported to the shaded area within the circle; sample points $OO$, $PP$, $P^{\mathrm{\prime }}P\text{'}$, and $BB$ are identified in the figure to illustrate the teleportation rule.

Figure D.1: Sample input 1, illustrating the downsizing process

Given a convex polygonal shape not containing any interior point of the cell, Adam would like to know the area of the corresponding teleported shape. Can you help?

입력

The first line of input contains three integers $x_{0}x\_0$, $y_{0}y\_0$, and $rr$, $-{10}^4\le x_0,y_0,r\le {10}^4-10^4\; \backslash leq\; x\_0,y\_0,r\; \backslash leq\; 10^4$, specifying the center of the circular cell and its radius. (The entire circular cell lies within the specified bounds.) The second line of input contains a positive integer $nn$, $3\le n\le 1003\; \backslash leq\; n\; \backslash leq\; 100$, followed by $nn$ pairs of integers $x_{1}x\_1$, $y_{1}y\_1$, $x_{2}x\_2$, $y_{2}y\_2$, \ldots, $x_{n}x\_n$, $y_{n}y\_n$, $-{10}^4\le x_i,y_i\le {10}^4-10^4\; \backslash leq\; x\_i,\; y\_i\; \backslash leq\; 10^4$, giving the vertices of a convex polygon with $nn$ vertices in counterclockwise order.

출력

Output the area of the region of the cell corresponding to the rectangular region in the input. Your answer should be correct to a relative or absolute error of ${10}^{-6}10^\{-6\}$.

3 3 5
5 11 9 9 6 9 1 13 1 13 6

4.112904