当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
6179：Rotating Line
题目描述
There are n points and one line in the 2D plane. Three points can be collinear.
You 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.
You 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 contains an integer T (≤100), the number of test cases.
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).
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).
输出解释
Each test case, you must output Q lines and each line contains a pair of integer, the coordinate of qi-th rotation centre.
输入样例
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
输出样例
-1 2 1 0 0 0 0 1 2 0 -1 0 0 1
提示
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).
来自杭电HDUOJ的附加信息
| Recommend | liuyiding |
最后修改于 2020-10-25T23:29:04+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 4000/2000MS(Java/Others) | 152428/152428K(Java/Others) |
登陆或注册以提交代码