1788. Rotating Line
时间限制 2000 ms 内存限制 149 MBYou can rotate the line anti-clockwise, but the rotation centre can be changed every time. The centre must be one of the n points.
Initially the centre is (0, 0) (of course, (0, 0) must be one of the n points), and the line coincides with y axis.
If there is only one point in the line, the line's rotation centre must be this point.
If the line meets another points, the centre may change to the other point.
If there are k points in this line and the current rotation centre is the p-th point of them (of course, we assume that the k points have already sorted), the next rotation centre will be the (k-p+1)-th point of them.
If p = k - p + 1, we consider that the rotation centre is not changed.
In this problem, you must find the q-th rotation centre's coordinate.
It is guaranteed that the q-th rotation centre always exists.
输入数据
The first line of each test case contains an integer n (1 <= n <= 3000, sum of n over all test cases does not exceed 10000) , the number of points.
The i-th line of the following n lines contains two integers x, y (-100 <= x, y <= 100), the coordinate of the i-th point. One of these n points is (0, 0).
Every two points are different and three points can be collinear.
And the next line contains an integer Q, the number of queries (sum of Q over all test cases does not exceed 10000).
Then Q integers ($q_i$) follow, described above (0 < $q_i $<= 1e9).
输出数据
样例输入
1 8 0 0 -1 0 -1 2 0 -1 0 1 0 2 1 0 2 0 7 1 2 3 4 5 6 7\n \n · \n · \n · \n · \n · \n · \n · \n · \n \n · · · · · · \n
样例输出
-1 2 1 0 0 0 0 1 2 0 -1 0 0 1· \n · \n · \n · \n · \n · \n · \n
样例说明
Initial rotation centre is (0, 0), and the first rotation centre is (-1, 2), because this line meets (-1, 2) at first.
Then the line meets 2 points (0, 1) and (1, 0), so that there are three points on the line. (-1, 2) is the 1st point of them, so the centre has to change to 3rd point (1, 0),
this is the second rotation centre.
Then the line meets 3 points (-1, 0), (0, 0), (2, 0), so that there are four points on the line. The centre is 3rd point of them, so the next centre will be 2nd point (0, 0),
this is the third rotation centre.
The fourth rotation centre is (0, 1) and the line meets 2 points (-1, 2) and (1, 0).
The centre is 2nd point of 3 points, so the centre was not changed. Then the line meets (2, 0), so the fifth rotation centre is (2, 0).