#P18595. Range Closest Pair of Points Query

Range Closest Pair of Points Query

Range Closest Pair of Points Query

平面最近点对问题是计算几何中的经典问题。

现在,欧几里得平面上有 nn 个点 p1,p2,…,pnp_1,p_2,\ldots,p_n。点 pip_i 的坐标为 (xi,yi)(x_i,y_i)。你需要回答 qq 个询问。

每个询问给出两个整数 l,rl,r,其中 1≤l<r≤n1\le l<r\le n。请在满足

l≤u<v≤rl\le u<v\le r

的所有点对中,求欧几里得距离最小的一对。你需要输出其距离的平方,即

(xu−xv)2+(yu−yv)2.(x_u-x_v)^2+(y_u-y_v)^2.

不同编号的点可以具有相同的坐标,此时距离可以为 00。

输入格式

第一行两个整数 n,qn,q,分别表示点数和询问数。

接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i,表示点 pip_i 的坐标。

接下来 qq 行,每行两个整数 l,rl,r,表示一个询问。

输出格式

对每个询问按输入顺序输出一行一个整数,表示该区间的最近点对距离的平方。

数据范围

  • 2≤n≤250 0002\le n\le250\,000;
  • 1≤q≤250 0001\le q\le250\,000;
  • 1≤xi,yi≤1081\le x_i,y_i\le10^8;
  • 每个询问满足 1≤l<r≤n1\le l<r\le n。

样例输入 1

5 5
2 4
1 1
3 3
5 1
4 2
1 5
2 3
2 4
3 5
1 3

样例输出 1

2
8
8
2
2

样例输入 2

2 1
1 1
1 1
1 2

样例输出 2

0