Problem I
Rocket Blocker

Public domain CC0 on rawpixel

Ivan is once again playing his favorite video game, Stellar Skirmishes: The Game. He needs to choose a landing site for a supply rocket, which has a circular cross section with radius $r$. The landing site is a ten meter by ten meter square, and consists of all points where the center of the rocket could potentially touch down. However, many landing sites contain rocks. For simplicity, we will consider landing sites with only a single rock, modeled as a convex 2D polygon. It would be really bad if the rocket came down on top of a rock at all, since it might cause the rocket to tip over. Hence, for a given landing site, Ivan needs to assess the probability that any part of the rocket will touch any part of the rock, assuming the rocket’s touchdown point (i.e. the center of its circular cross-section) is chosen uniformly at random from anywhere in the landing site.

Input

The first line of input consists of a single floating-point number $r$ ($0 < r \leq 100$), the radius of the rocket in centimeters. The next line contains a single integer $n$ ($3 \leq n \leq 50$), the number of vertices of the polygonal rock. The following $n$ lines each contain two space-separated floating-point numbers $x_i$ and $y_i$ ($-500 + r \leq x_i,y_i \leq 500 - r$) specifying the coordinates of one vertex, measured in centimeters from the center of the landing site. The landing site itself is always a square $1000$ centimeters on a side, with coordinates extending from $(-500,-500)$ to $(500,500)$. Note that the vertices of the rock are guaranteed to be located at least $r$ centimeters away from the edges of the landing site.

The rock is guaranteed to be convex, with no three vertices collinear, and the vertices will be given in counterclockwise order going around the rock.

Output

Output a single floating-point number giving the probability (between 0.0 and 1.0) that the rocket will intersect the rock at all, if the rocket’s center is chosen uniformly at random from anywhere in the square landing site. (The entire rocket does not have to be on the landing site, only its center.) Your answer must be correct to within an absolute or relative error of at most $10^{-6}$.

100
4
100 100
-100 100
-100 -100
100 -100

0.15141592653589794

9.818646743965298
5
388.0423666565624 -299.7392539844666
-272.4696378079444 341.6745137897658
-386.25237080202317 302.1638322638671
102.16349299402083 -361.3559642251183
244.1757856258959 -355.84620907506473

0.18454429004731557