#PQJ1835x9613. QOJ 1835_9613
QOJ 1835_9613
标题: 计算几何 - Problem - QOJ.ac
#9613. 计算几何
The problem was used in the following contests:
题目描述
给定一个包含 n 个点的序列,第 i 个点的坐标为 (ai,bi) 。
共有 q 次询问,每次询问一个区间 [l,r] ,你需要求出下面式子的值。
mini=lrminj=i+1r(|ai−aj|+|bi−bj|)
保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。
输入格式
第一行输入两个正整数 n,q 。
接下来 n 行,每行输入两个整数 ai,bi ,表示第 i 个点的坐标为 (ai,bi) 。
接下来 q 行,每行输入两个正整数 l,r ,表示询问区间 [l,r] 。
输出格式
输出 q 行,每行包含一个非负整数,表示答案。
样例一输入
4 5
1 1
2 2
1 2
2 1
1 4
1 3
1 2
2 3
3 4
样例一输出
1
1
2
1
2
样例二
见下发文件下的 geo2.in 与 geo2.ans 。
该样例约束与测试点 2 一致。
样例三
见下发文件下的 geo3.in 与 geo3.ans 。
该样例约束与测试点 18 一致。
下发文件
本题下发的文件除三个样例外还有 rand.cpp 。
rand.cpp 是一个数据生成器,与生成评测用例的数据生成器仅有随机种子不同。
输入 n,q,A,B 后数据生成器才可生成整个数据,数据输出到 geo.in ,其中 A,B 分别表示 |ai| 与 |bi| 的上界。
数据范围
对于所有测试点, 2≤n≤106 , 1≤q≤106 , |ai|,|bi|≤109 , 1≤l<r≤n ,保证 ai,bi,l,r 在指定范围内用指定方式随机生成。
测试点表格
测试点编号 n≤ q≤ 1∼2 2×103 2×103 3∼8 2×104 2×104 9∼14 2×105 2×105 15∼16 2×103 106 17∼19 106 10 20∼25 106 106
对于每一档部分分,设其测试点编号范围为 l∼r ,则测试点 l+1∼r−1 满足 |ai|,|bi|≤106 ,测试点 ⌊l+r2⌋+1∼r 满足 bi=0 。
提示
本题输入输出规模较大,请使用较为快速的输入输出方式。