#P4541. [Hnoi2016]矿区

    ID: 2920 传统题 3000ms 512MiB 尝试: 625 已通过: 159 难度: 9 上传者: 标签>难度分类省选/NOI-图论半边面遍历排序与序列处理自定义排序规则计算几何鞋带公式平面图对偶动态规划树形 DP组合数学贡献法二分查找数论欧几里得算法CF2800对偶图

[Hnoi2016]矿区

[HNOI2016] 矿区

题目描述

矿区可视为一张连通平面图。边是连接整数坐标点的线段。图划分出的每个有界面是一个开发区域,面积为 ss 的区域有矿量 s2s^2。

每个开采计划指定一个由若干开发区域组成的多边形,只给出多边形的边界。计划的优先度等于所选开发区域的矿量之和除以面积之和。例如,若计划包括两个面积分别为 a,ba,b 的区域,优先度就是 (a2+b2)/(a+b)(a^2+b^2)/(a+b)。

请按给出的顺序计算每个计划的优先度,输出最简分数。下一个计划的输入用上一个计划的答案编码。

输入格式

第一行三个正整数 n,m,kn,m,k,分别表示点数、边数和开采计划数。

接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i,表示点 ii 的坐标 (xi,yi)(x_i,y_i)。

接下来 mm 行,每行两个正整数 a,ba,b,表示点 a,ba,b 之间有一条边。

其后的一行整数依次描述 kk 个计划。设 PP 是上一计划答案的最简分数的分子。处理第一个计划时令 P=0P=0。每个计划先给出整数 cc,边界点数为

d=(c+P) mod n+1.d=(c+P)\bmod n+1.

接下来读入 dd 个整数 z1,…,zdz_1,\ldots,z_d。边界点按照逆时针顺序给出,第 ii 个点的编号为 (zi+P) mod n+1(z_i+P)\bmod n+1。边界最后一个点再与第一个点相连。

输出格式

对每个计划输出一行两个正整数,用空格分隔,分别是优先度最简分数的分子和分母。

数据范围

n,k≤2×105n,k\le 2\times10^5,m≤3n−6m\le 3n-6,∣xi∣,∣yi∣≤3×104|x_i|,|y_i|\le 3\times10^4。

所有计划的 dd 之和不超过 2×1062\times10^6。每个计划包含至少一个开发区域,所含区域构成一个连通块。所有开发区域的矿量之和不超过 263−12^{63}-1。保证平面图中没有多余的点和边,输入合法。

样例

9 14 5
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
1 2
2 3
5 6
7 8
8 9
1 4
4 7
5 8
3 6
6 9
4 8
1 5
2 6
6 8
3 3 0 4 7 1 3 4 6 4 8 0 4 3 6 2 3 8 0 4 6 2 5 0 4 5 7 6 3
1 1
1 2
1 1
9 10
3 4

样例说明

样例中的九个点与十四条边

第一项计划中,P=0,n=9,c=3P=0,n=9,c=3,所以 d=(3+0) mod 9+1=4d=(3+0)\bmod9+1=4。接下来四个数 3,0,4,73,0,4,7 解码为点 4,1,5,84,1,5,8。优先度为 1/11/1。

计划 逆时针边界点编号
1 4,1,5,84,1,5,8
2 5,6,85,6,8
3 1,2,6,5,8,41,2,6,5,8,4
4 1,2,6,8,41,2,6,8,4
5 1,5,6,8,7,41,5,6,8,7,4