Closed Paths

JFantasy has fallen in love with a beautiful girl (An ICPC volunteer?). Every afternoon, when the sun set, the girl comes out from her dorm, walks around the campus, and returns to her dorm. The girl’s walking path can be considered as a closed polyline. A closed polyline is a curve specified by a sequence of points (P₁, P₂, …, P_n) so that the curve consists of the line segments P₁P₂, P₂P₃, …, P_n-1P_n, P_nP₁. Note that two line segments may intersect, coincide or partially coincide with each other. The points P₁, P₂, …, P_n are also called vertices of the polyline. While the girl is walking along the path, JFantasy is standing at some point which is not lying on the path. During the girl’s walking, the spoony boy rotates himself such that he can always see the girl directly in front of him. The boy may sometimes rotate counter-clockwise, and sometimes rotate clockwise. If the boy stands at point P, let AP denote the total degrees the boy rotate counter-clockwise, and BP denote the total degrees the boy rotate clockwise. It is not difficult to see that A_P – B_P is a multiple of 360, because when the girl finishes walking, the boy faces in the same direction as when the girl starts walking. We define the rotation number of P to be (A_P – B_P) / 360.

LCQ is one of JFantasy’s G (G for good) friends. He has found JFantasy’s secret, and got an idea of making fun of him. He wants to put JFantasy at some point of which the rotation number is maximum given the walking path of the girl. To simplify the problem, we assume that the point where JFantasy can be put must be on a straight line. Formally, the problem can be stated as follows: Given the coordinates of (P₁, P₂, …, P_n), which specifies the girl’s walking path, you are asked to find the largest possible rotation number among all the points that are on the X axis, but not on the girl’s walking path.

The input begins with a line containing an integer T (T<=100), which indicates the number of test cases. Each case begins with a line containing an integer N (2<=N<=1000), indicating the number of vertices of the girl’s walking path. The following N lines each contain two integers x_i and y_i (-1000<= x_i, y_i <=1000), indicating the coordinates of the ith vertex P_i.

For each case, output the largest possible rotation number in a line.

3
2
1 2
2 1
6
1 -1
2 -1
2 1
3 1
3 0
1 0
5
1 1
-1 0
1 -1
0 1
0 -1

0
0
2

SYSU

2014 Multi-University Training Contest 9