{"problem":{"name":"[ICPC 2022 Jinan R] Grid Points","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9672"},"statements":[{"statement_type":"Markdown","content":"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$. \n\nConsider all grid points in the polygon. Order them in increasing order of $\\textbf{slopes}$. Output the $k$-th grid point in this order. \n\nA 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)$.\n\n## Input\n\nThe first line contains one integer $T~(1\\le T \\le 500)$, the number of test cases.\n\nFor 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.\n\nIt 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.\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $2000$.\n\n## Output\n\nFor each test case, output two integers $x, y$ in one line representing the coordinate $(x, y)$ of the $k$-th grid point.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9672","tags":["2022","O2优化","ICPC","类欧几里得算法","济南"],"sample_group":[["4\n3 3\n1 1\n3 1\n3 3\n4 500000000000000000\n1 1\n1000000000 1\n1000000000 1000000000\n1 1000000000\n9 22\n9 6\n6 7\n9 7\n10 10\n6 9\n3 9\n1 6\n1 5\n7 3\n5 22447972861454999\n270353376 593874603\n230208698 598303091\n237630296 255016434\n782669452 568066304\n654623868 958264153","3 2\n500000000 500000000\n7 8\n730715389 644702744"]],"created_at":"2026-03-03 11:09:25"}}