John wants to put a hidden camera in a room. For this problem, we ignore the vertical dimension and treat the room as a two-dimensional object. The room has the shape of a convex polygon. The camera is placed on a wall, halfway between two corners. The camera has a limited view: the borders of the view are given by the two lines that intersect the wall at a 45 degree angle. John wants to know how much of the room is visible to the camera. Can you help him?
On the first line one positive number: the number of test cases, at most 100. After that per test case:
one line with a single integer $n$ ($3 \leq n \leq 1\, 000$): the number of corners of the room.
$n$ lines with two space-separated integers $x$ and $y$ ($-10\, 000 \leq x,y \leq 10\, 000$): the coordinates of the corners.
The corners are given in counterclockwise order. All angles are strictly between $0$ and $180$ degrees. The camera is placed exactly halfway between the first two corners in the input.
Per test case:
one line with one floating point number: the ratio of the area that the camera can see and the total area of the room. This number should be accurate up to $10^{-6}$ relative or absolute precision.
Sample Input 1 | Sample Output 1 |
---|---|
2 5 -3 0 3 0 4 5 -2 8 -5 3 4 0 2 2 0 3 1 1 3 |
0.7125 0.5 |