Little D wants to build a prism palace using two parallel planes $$$A(z=0)$$$ and $$$B(z=10^9)$$$ that she has. To finish her build, she borrows a convex polygon $$$P$$$ consisting of $$$n$$$ points from Little N. She puts two identical copies of $$$P$$$ on the two planes, one on each. The two polygons must be identical to $$$P$$$ and must be able to coincide by translating the polygon on $$$A$$$ along some vector $$$(d_x, d_y, 10^9)$$$ to the polygon on $$$B$$$ without rotating.
Together, the two polygons form a prism-shaped palace between them. Let the projection area of the prism's sides perpendicularly onto plane $$$A$$$ be $$$S_1,S_2,\cdots S_n$$$, and the probability of the multiset $$$\{S_i\}$$$ being cool be $$$f(r)$$$, assuming that $$$(d_x, d_y)$$$ is chosen uniformly at random from the circle centered at $$$(0,0)$$$ with a radius $$$r$$$, i.e., $$$d_x^2 + d_y^2 \le r^2$$$. Here, a multiset of real numbers $$$S$$$ is cool if there exists an element $$$x$$$ in $$$S$$$ such that $$$\sum\limits_{y\in S}y=2x$$$. It can be proved that the limit $$$\lim_{r \rightarrow \infty} f(r)$$$ does exist, and you need to find this limit.
The first line of input contains a single integer $$$n$$$ ($$$3\leq n\leq 2\times 10^5$$$), denoting the number of vertices of polygon $$$P$$$.
The next $$$n$$$ lines each contain two integers $$$(x_i,y_i)$$$ ($$$|x_i|,|y_i|\leq 10^9$$$), denoting the vertices of polygon $$$P$$$. The polygon $$$P$$$ is formed by connecting $$$(x_i,y_i)$$$ and $$$(x_{i\bmod n+1},y_{i\bmod n+1})$$$ where $$$1\leq i\leq n$$$. It is guaranteed that the polygon is convex, i.e., every inner angle of the polygon is smaller than $$$\pi$$$.
The output contains only one real number, denoting your answer.
Let your output be $$$u$$$, and the answer be $$$p$$$. You'll get accepted if and only if $$$\frac{|u-p|}{\max(1,p)}\leq 10^{-6}$$$.
3 0 0 1 0 0 1
1.000000000000000
4 0 0 0 1 1 1 1 0
0.000000000000000
4 0 0 0 3 1 2 1 1
0.500000000000000
For the first test case, you can see that whatever the two polygons' positions are, the largest of the three projection areas is always the sum of the other two, so the answer is $$$100\%$$$, or $$$1.0$$$.
