P2093 [CTT] JZPFAR

For the original "Parts Grouping", see P1233.

There are $n$ points on the plane. There are $m$ queries. In each query, given a point $(px, py)$ and an integer $k$, output the index of the $k$-th farthest point from $(px, py)$ among the $n$ points. If two (or more) points have the same distance to $(px, py)$, then the point with the smaller index is considered farther.

The first line contains an integer $n$, the number of points. The next $n$ lines each contain two integers $x_i, y_i$, the coordinates of the $n$ points. The indices of the points follow the input order and are $1\ldots n$. The next line contains an integer $m$, the number of queries. The next $m$ lines each contain three integers $px_i, py_i, k_i$, describing a query.

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

- Constraints and Notes. - In $50\%$ of the testdata, the coordinates of the $n$ points are randomly distributed within some range. - In $100\%$ of the testdata, $1\le n\le 10^5$, $1\le m\le 10^4$, $1\le k\le 20$, $-10^9\le x_i, y_i, px_i, py_i\le 10^9$. Any two points among the $n$ points have different coordinates. The coordinates of the query points in the $m$ queries are randomly distributed within some range. Translated by ChatGPT 5