← 返回题目列表

Codeforces · 1195/F

F. 几何匿名俱乐部

中文机器翻译题面 查看原题

Denis 在 SIS 召开几何匿名俱乐部会议。他为俱乐部准备了$$$n$$$个凸多边形,编号从$$$1$$$到$$$n$$$。他计划让俱乐部成员计算这些多边形的闵可夫斯基和。更准确地说,他计划给 $$$q$$$ 任务,其中第 $$$i$$$ 要求计算索引从 $$$l_i$$$ 到 $$$r_i$$$ 的多边形的 Minkowski 总和。

两个集合 $$$A$$$ 和 $$$B$$$ 的 Minkowski 之和是集合 $$$C = \{a + b : a \in A, b \in B\}$$$。可以证明,如果$$$A$$$和$$$B$$$是凸多边形,那么$$$C$$$也将是凸多边形。

两个凸多边形的总和

要计算 $$$p$$$ 多边形 ($$$p > 2$$$) 的 Minkowski 和,您需要计算前 $$$p - 1$$$ 多边形的 Minkowski 和,然后计算结果多边形和第 $$$p$$$ 个多边形的 Minkowski 和。

为了方便检查答案,Denis决定为他准备的每个任务准备并计算Minkowski和中的顶点数。帮助他做到这一点。

输入

输入的第一行包含一个整数 $$$n$$$ — Denis 准备的凸多边形的数量 ($$$1 \le n \le 100\,000$$$)。

然后是 $$$n$$$ 凸多边形。第 $$$i$$$ 个多边形的描述以一个整数 $$$k_i$$$ 开始 — 第 $$$i$$$ 个多边形中的顶点数 ($$$3 \le k_i$$$)。接下来的 $$$k_i$$$ 行包含两个整数 $$$x_{ij}$$$、$$$y_{ij}$$$ — 每个为逆时针顺序第 $$$i$$$ 个多边形的顶点坐标 ($$$|x_{ij}|, |y_{ij}| \le 10 ^ 9$$$)。

保证不存在三个连续的顶点位于同一条线上。所有多边形的顶点总数不超过$$$300\,000$$$。

下面一行包含一个整数 $$$q$$$ — 任务数量 ($$$1 \le q \le 100\,000$$$)。接下来的 $$$q$$$ 行包含任务的描述。第 $$$i$$$ 任务的描述包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

输出

对于每个任务,打印一个整数 - 索引从 $$$l_i$$$ 到 $$$r_i$$$ 的多边形 Minkowski 总和中的顶点数。

示例

输入 #1

3
3
0 0
1 0
0 1
4
1 1
1 2
0 2
0 1
3
2 2
1 2
2 1
3
1 2
2 3
1 3

输出 #1

5
5
6

注意

示例说明:

示例中的第一个、第二个和第三个多边形

第一个和第二个、第二个和第三个以及所有多边形的 Minkowski 和