#PQJ1835x9613. QOJ 1835_9613

    ID: 2724 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测计算几何前缀和

QOJ 1835_9613

标题: 计算几何 - Problem - QOJ.ac

#9613. 计算几何

Statistics

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 。

提示

本题输入输出规模较大,请使用较为快速的输入输出方式。