Problem A
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\mathrm{\%}$ 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\le n\le 1000$): the number of corners of the room.

• $n$ lines with two space-separated integers $x$ and $y$ ($-10000\le x,y\le 10000$): 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