P4357 [CQOI2016] K-th Farthest Pair

Given the coordinates of $N$ points in the plane, find the $K$-th farthest pair under the Euclidean distance. The Euclidean distance between two points $P(x_1,y_1)$ and $Q(x_2,y_2)$ is defined as $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

The first line contains two integers $N,K$ separated by a space. The next $N$ lines each contain two integers $X,Y$, representing the coordinates of a point.

Output a single integer on the first line, which is the square of the distance of the $K$-th farthest pair (it is guaranteed to be an integer).

For $100\%$ of the testdata, $N \le 100000,1 \le K \le 100,K \le \dfrac {N(N-1)}{2},0 \le X,Y < 2^{31}$. Translated by ChatGPT 5