#P9672. [ICPC 2022 Jinan R] Grid Points

    ID: 10954 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2022O2优化ICPC类欧几里得算法济南

[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 (x,y)(x, y) of any point in the polygon satisfies x>0x> 0 and y>0y> 0.

Consider all grid points in the polygon. Order them in increasing order of \textbf{slopes}. Output the kk-th grid point in this order.

A grid point is a point (x,y)(x, y) such that xx and yy are integers. A point on the boundary of a polygon is considered to be in the polygon. The slope of point (x,y)(x, y) is y/xy/x. If two points have the same slope, they are ordered lexicographically first by xx, then by yy. In other words, a point (x1,y1)(x_1, y_1) is lexicographically less than (x2,y2)(x_2, y_2) if (x1<x2)(x1=x2y1<y2)(x_1<x_2)\vee (x_1=x_2 \wedge y_1<y_2).

输入格式

The first line contains one integer T (1T500)T~(1\le T \le 500), the number of test cases.

For each test case, the first line contains two integers n,k (n3,1k)n, k~(n\ge 3, 1\le k). Each of the next nn lines describes a vertex of the polygon. Each vertex is denoted by two integers x,y (1x,y109)x, y~(1\le x, y\le 10^9), representing its coordinate (x,y)(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 11 point. It is guaranteed that kk is no more than the number of grid points in the polygon.

It is guaranteed that the sum of nn over all test cases is no more than 20002000.

输出格式

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