[ICPC2022 Jinan R] Grid Points

## 题目描述 在笛卡尔平面的第一个象限中，您会得到一个简单的多边形。这意味着多边形中任何点的坐标$（x，y）$满足$x>0$和$y>0$。 考虑多边形中的所有网格点。按\textbf｛斜率｝的递增顺序排列。按此顺序输出第$k$个网格点。 网格点是一个点$（x，y）$，使得$x$和$y$是整数。多边形边界上的一个点被认为在多边形中。点$（x，y）$的斜率为$y/x$。如果两个点具有相同的斜率，则它们首先按字典顺序排列$x$，然后按$y$。换句话说，如果$（x_1<x_2）\vee（x_1=x_2\wedge y_1<y_2）$，则点$（x_1，y_1）$在字典上小于$（x_2，y_2）。 ## 输入格式 第一行包含一个整数$T~（1\le T\le 500）$，即测试用例的数量。 对于每个测试用例，第一行包含两个整数$n，k~（n\ge 3，1\le k）$。接下来的每一条$n$线都描述了多边形的一个顶点。每个顶点由两个整数$x，y~（1\le x，y\le 10^9）$表示，表示其坐标$（x，y）$。顶点按逆时针顺序排列。 保证多边形是简单的，即顶点是不同的，两条边只有在边界上连续时才能重叠，并且重叠恰好包含$1$点。可以保证$k$不超过多边形中的网格点数。 保证所有测试用例的总金额不超过2000美元。 ## 输出格式 对于每个测试用例，在一行中输出两个整数$x，y$，表示第$k$个网格点的坐标$（x，y）$。 ## 输入输出样例 ### 输入 #1 ``` 4 3 3 1 1 3 1 3 3 4 5000000000000000 1 1 1000000000 1 1000000000 1000000000 100000000 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 ``` ### 输出 #1 ``` 3 2 500000000 500000000 7 8 730715389 644702744 ```

You are given a simple polygon in the first quadrant of the Cartesian plane. This means that the coordinate $(x, y)$ of any point in the polygon satisfies $x> 0$ and $y> 0$. Consider all grid points in the polygon. Order them in increasing order of \textbf{slopes}. Output the $k$-th grid point in this order. A grid point is a point $(x, y)$ such that $x$ and $y$ are integers. A point on the boundary of a polygon is considered to be in the polygon. The slope of point $(x, y)$ is $y/x$. If two points have the same slope, they are ordered lexicographically first by $x$, then by $y$. In other words, a point $(x_1, y_1)$ is lexicographically less than $(x_2, y_2)$ if $(x_1<x_2)\vee (x_1=x_2 \wedge y_1<y_2)$.

The first line contains one integer $T~(1\le T \le 500)$, the number of test cases. For each test case, the first line contains two integers $n, k~(n\ge 3, 1\le k)$. Each of the next $n$ lines describes a vertex of the polygon. Each vertex is denoted by two integers $x, y~(1\le x, y\le 10^9)$, representing its coordinate $(x, y)$. 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 $1$ point. It is guaranteed that $k$ is no more than the number of grid points in the polygon. It is guaranteed that the sum of $n$ over all test cases is no more than $2000$.

For each test case, output two integers $x, y$ in one line representing the coordinate $(x, y)$ of the $k$-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