[Ynoi2002] Adaptive Hsearch&Lsearch
题目描述
有 $n$ 个点 $p_1,p_2,\dots,p_n$ 在二维平面上。
有 $q$ 次询问,在第 $i$ 个询问中,给定两个数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$),你需要找到一对 $(u,v)$ 满足 $l_i\leq u<v\leq r_i$,$p_u$ 和 $p_v$ 之间的欧几里得距离 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最小。
输入输出格式
输入格式
第一行两个数 $n,q$ 表示点数以及询问数。
之后 $n$ 行,第 $i$ 行包含两个整数 $x_i,y_i$ 表示 $p_i$ 的坐标。
之后 $q$ 行,第 $i$ 行包含两个整数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$) 表示第 $i$ 个询问。
输出格式
对每个询问,输出一行一个整数表示最小的 $(x_u-x_v)^2+(y_u-y_v)^2$。
输入输出样例
输入样例 #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
说明
Idea:Claris,Solution:Claris,Code:Claris,Data:Claris&nzhtl1477
对于 $100\%$ 的数据,满足 $2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$,$1\leq x_i,y_i\leq 10^8$。