#P9672. [ICPC 2022 Jinan R] Grid Points
[ICPC 2022 Jinan R] Grid Points
题目描述
You are given a simple polygon in the first quadrant of the Cartesian plane. This means that the coordinate of any point in the polygon satisfies and .
Consider all grid points in the polygon. Order them in increasing order of \textbf{slopes}. Output the -th grid point in this order.
A grid point is a point such that and are integers. A point on the boundary of a polygon is considered to be in the polygon. The slope of point is . If two points have the same slope, they are ordered lexicographically first by , then by . In other words, a point is lexicographically less than if .
输入格式
The first line contains one integer , the number of test cases.
For each test case, the first line contains two integers . Each of the next lines describes a vertex of the polygon. Each vertex is denoted by two integers , representing its coordinate . The vertices are given in counterclockwise order.
It is guaranteed that the polygon is simple, i.e.~ the vertices are distinct, two edges may overlap only when they are consecutive on the boundary, and the overlap contains exactly point. It is guaranteed that is no more than the number of grid points in the polygon.
It is guaranteed that the sum of over all test cases is no more than .
输出格式
For each test case, output two integers in one line representing the coordinate of the -th grid point.
4
3 3
1 1
3 1
3 3
4 500000000000000000
1 1
1000000000 1
1000000000 1000000000
1 1000000000
9 22
9 6
6 7
9 7
10 10
6 9
3 9
1 6
1 5
7 3
5 22447972861454999
270353376 593874603
230208698 598303091
237630296 255016434
782669452 568066304
654623868 958264153
3 2
500000000 500000000
7 8
730715389 644702744