#P18595. Range Closest Pair of Points Query
Range Closest Pair of Points Query
Range Closest Pair of Points Query
平面最近点对问题是计算几何中的经典问题。
现在,欧几里得平面上有 个点 。点 的坐标为 。你需要回答 个询问。
每个询问给出两个整数 ,其中 。请在满足
的所有点对中,求欧几里得距离最小的一对。你需要输出其距离的平方,即
不同编号的点可以具有相同的坐标,此时距离可以为 。
输入格式
第一行两个整数 ,分别表示点数和询问数。
接下来 行,第 行两个整数 ,表示点 的坐标。
接下来 行,每行两个整数 ,表示一个询问。
输出格式
对每个询问按输入顺序输出一行一个整数,表示该区间的最近点对距离的平方。
数据范围
- ;
- ;
- ;
- 每个询问满足 。
样例输入 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