Natsu is eating bread at Sensei's café when a piece of bread falls onto the floor and starts rolling.
The fallen bread can be regarded as a convex polygon in a two-dimensional plane. Its $$$n$$$ vertices, listed in counterclockwise order, are $$$A_1,A_2,\ldots,A_n$$$. The vertices are pairwise distinct, and no three vertices are collinear. The floor can be regarded as the horizontal line $$$y=0$$$.
Initially, the bread touches the floor along edge $$$(A_n,A_1)$$$. Let the position of vertex $$$A_n$$$ at this moment be the origin. The bread rolls in the positive direction of the $$$x$$$-axis; that is, $$$A_n=(0,0)$$$ and $$$A_1=(x_1,0)$$$, where $$$x_1 \gt 0$$$. The bread then starts rolling. The rolling process can be abstracted as an infinite sequence of rotations performed in order. In the $$$i$$$-th rotation, the entire bread is rotated clockwise about the current position of vertex $$$A_{((i-1)\bmod n)+1}$$$ until $$$A_{(i\bmod n)+1}$$$ touches the floor for the first time, that is, until its $$$y$$$-coordinate becomes $$$0$$$ for the first time.
As a romantic philosopher, Natsu considers the rolling of the bread to be a coincidental and romantic event. For the sake of this romance, after the $$$k$$$-th rotation, Natsu records the distance $$$L(k)$$$ rolled by the bread and the area $$$S(k)$$$ swept out by the bread. You need to calculate their ratio as $$$k$$$ tends to infinity, namely:
$$$$$$ \lim_{k\to +\infty}\frac{S(k)}{L(k)} $$$$$$
The distance $$$L(k)$$$ rolled by the bread after the $$$k$$$-th rotation is defined as the distance from the origin to the position of vertex $$$A_{(k\bmod n)+1}$$$ when the $$$k$$$-th rotation ends. The area $$$S(k)$$$ swept out by the bread after the $$$k$$$-th rotation is defined as the area of the union of all regions covered by the convex-polygon bread at all moments from the beginning of the first rotation to the end of the $$$k$$$-th rotation.
The first line contains one positive integer $$$T$$$ $$$(1\leq T\leq 10^3)$$$, denoting the number of test cases.
For each test case, the first line contains one integer $$$n$$$ $$$(3\leq n\leq 10^5)$$$, denoting the number of vertices of the convex-polygon bread.
The next $$$n$$$ lines each contain two integers $$$x_i,y_i$$$ $$$(0\leq |x_i|,y_i\leq 10^9)$$$. The $$$i$$$-th line denotes the coordinates of vertex $$$A_i$$$ when the bread has just fallen onto the floor.
It is guaranteed that $$$y_1$$$, $$$x_n$$$, and $$$y_n$$$ are all $$$0$$$, and that $$$x_1 \gt 0$$$.
It is guaranteed that vertices $$$A_1,A_2,\ldots,A_n$$$ are pairwise distinct, no three vertices are collinear, and they form a convex polygon in counterclockwise order.
It is guaranteed that the sum of $$$n$$$ over all test cases in one test file does not exceed $$$3\times 10^5$$$.
For each test case, output one floating-point number on one line, denoting the answer. Your answer is considered correct if and only if its relative or absolute error compared with the standard answer does not exceed $$$10^{-9}$$$.
Suppose that your answer is $$$a$$$ and the standard answer is $$$b$$$. Your answer is considered correct if
$$$$$$ \frac{|a-b|}{\max\{b,1\}}\leq 10^{-9} $$$$$$
232 01 50 041 01 10 10 0
4.9086645199411971.384172075579563
For the first test case, the process from the beginning of the first rotation to the end of the fourth rotation is shown below:
When $$$k=4$$$, we have:
$$$$$$ \begin{aligned} L(k)&=4+3\sqrt{26}\approx19.297058541 \\ S(k)&=\frac{120}{13}+13\sqrt3+\frac{91\pi}{6} +43\arctan\frac15 \approx87.882927382 \end{aligned} $$$$$$
