28174번 - Range Closest Pair of Points Query 다국어

The closest pair of points problem is a well-known problem of computational geometry. In this problem, there are $n$ points $p_1,p_2,\ldots,p_n$ in the Euclidean plane. You will be given $q$ queries. In the $i$-th query, you will be given two integers $\ell_i$ and $r_i$ ($1\leq \ell_i< r_i\leq n$). You need to find a pair of points $(u,v)$ such that $\ell_i\leq u<v\leq r_i$ and the Euclidean distance $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ between point $p_u$ and $p_v$ is minimized.

The first line of the input contains two integers $n$ and $q$ ($2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$), denoting the number of points and the number of queries.

In the next $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1\leq x_i,y_i\leq 10^8$), describing the coordinates of $p_i$.

Each of the next $q$ lines contains two integers $\ell_i$ and $r_i$ ($1\leq \ell_i< r_i\leq n$), denoting a query.

For each query, print a single line containing an integer, denoting the value of $(x_u-x_v)^2+(y_u-y_v)^2$.