#P4541. [Hnoi2016]矿区
[Hnoi2016]矿区
[HNOI2016] 矿区
题目描述
矿区可视为一张连通平面图。边是连接整数坐标点的线段。图划分出的每个有界面是一个开发区域,面积为 的区域有矿量 。
每个开采计划指定一个由若干开发区域组成的多边形,只给出多边形的边界。计划的优先度等于所选开发区域的矿量之和除以面积之和。例如,若计划包括两个面积分别为 的区域,优先度就是 。
请按给出的顺序计算每个计划的优先度,输出最简分数。下一个计划的输入用上一个计划的答案编码。
输入格式
第一行三个正整数 ,分别表示点数、边数和开采计划数。
接下来 行,第 行两个整数 ,表示点 的坐标 。
接下来 行,每行两个正整数 ,表示点 之间有一条边。
其后的一行整数依次描述 个计划。设 是上一计划答案的最简分数的分子。处理第一个计划时令 。每个计划先给出整数 ,边界点数为
接下来读入 个整数 。边界点按照逆时针顺序给出,第 个点的编号为 。边界最后一个点再与第一个点相连。
输出格式
对每个计划输出一行两个正整数,用空格分隔,分别是优先度最简分数的分子和分母。
数据范围
,,。
所有计划的 之和不超过 。每个计划包含至少一个开发区域,所含区域构成一个连通块。所有开发区域的矿量之和不超过 。保证平面图中没有多余的点和边,输入合法。
样例
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
样例说明

第一项计划中,,所以 。接下来四个数 解码为点 。优先度为 。
| 计划 | 逆时针边界点编号 |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |