QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[+14]

# 9613. 计算几何

Statistics

题目描述

给定一个包含 n 个点的序列,第 i 个点的坐标为 (ai,bi)

共有 q 次询问,每次询问一个区间 [l,r] ,你需要求出下面式子的值。

min

保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。

输入格式

第一行输入两个正整数 n, q

接下来 n 行,每行输入两个整数 a_i, b_i ,表示第 i 个点的坐标为 (a_i, b_i)

接下来 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.ingeo2.ans

该样例约束与测试点 2 一致。

样例三

见下发文件下的 geo3.ingeo3.ans

该样例约束与测试点 18 一致。

下发文件

本题下发的文件除三个样例外还有 rand.cpp

rand.cpp 是一个数据生成器,与生成评测用例的数据生成器仅有随机种子不同。

输入 n, q, A, B 后数据生成器才可生成整个数据,数据输出到 geo.in ,其中 A, B 分别表示 |a_i||b_i| 的上界。

数据范围

对于所有测试点, 2 \le n \le 10^61 \le q \le 10^6|a_i|, |b_i| \le 10^91 \le l < r \le n ,保证 a_i, b_i, l, r 在指定范围内用指定方式随机生成。

测试点表格

测试点编号 n \le q \le
1 \sim 2 2 \times 10^3 2 \times 10^3
3 \sim 8 2 \times 10^4 2 \times 10^4
9 \sim 14 2 \times 10^5 2 \times 10^5
15 \sim 16 2 \times 10^3 10^6
17 \sim 19 10^6 10
20 \sim 25 10^6 10^6

对于每一档部分分,设其测试点编号范围为 l \sim r ,则测试点 l+1 \sim r-1 满足 |a_i|, |b_i| \le 10^6 ,测试点 \lfloor \frac{l+r}{2} \rfloor + 1 \sim r 满足 b_i = 0

提示

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