P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

There are $n$ points $p_1,p_2,\dots,p_n$ on a two-dimensional plane. There are $q$ queries. In the $i$-th query, two numbers $l_i,r_i$ are given ($1\leq l_i< r_i\leq n$). You need to find a pair $(u,v)$ such that $l_i\leq u

The first line contains two integers $n,q$, representing the number of points and the number of queries. The next $n$ lines each contain two integers $x_i,y_i$, representing the coordinates of $p_i$. The next $q$ lines each contain two integers $l_i,r_i$ ($1\leq l_i< r_i\leq n$), representing the $i$-th query.

For each query, output one integer per line, representing the minimum value of $(x_u-x_v)^2+(y_u-y_v)^2$.

Idea: Claris, Solution: Claris, Code: Claris, Data: Claris & nzhtl1477. For $100\%$ of the testdata, $2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$, $1\leq x_i,y_i\leq 10^8$. Translated by ChatGPT 5