Problem B
Hidden Camera

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?

Figure 1: The room as described in the first sample. The camera (the dot) can view the shaded region. The limits are given by lines that make a 45 degree angle with the base wall. The area of the shaded region is $71.25\% $ of the total area of the room.

Input

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.

Output

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.

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