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?
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 ≤ n ≤ 1000): the number of corners of the room.
n lines with two space-separated integers x and y (-10000 ≤ x, y ≤ 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.