Hide

# 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 $r$ is centered at a point $O$. Let $P$ be any point not in the interior of the cell, and suppose the line $\overline{OP}$ intersects the cell’s boundary at the point $B$. Then point $P$ is teleported to a point $P’$ lying on this line, where $\text {length}(\overline{OP})\cdot \text {length}(\overline{OP'}) = r^2$. (Points along the cell boundary are teleported to themselves.) Figure 1 shows how a pentagonal “house” is teleported to the shaded area within the circle; sample points $O$, $P$, $P’$, and $B$ are identified in the figure to illustrate the teleportation rule.

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?

## Input

The first line of input contains three integers $x_0$, $y_0$, and $r$, $-10^4 \leq x_0,y_0,r \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 $n$, $3 \leq n \leq 100$, followed by $n$ pairs of integers $x_1$, $y_1$, $x_2$, $y_2$, …, $x_ n$, $y_ n$, $-10^4 \leq x_ i, y_ i \leq 10^4$, giving the vertices of a convex polygon with $n$ vertices in counterclockwise order.

## Output

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}$.

Sample Input 1 Sample Output 1
3 3 5
5 11 9 9 6 9 1 13 1 13 6

4.112904

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.9hard
Statistics Show