#P11809. [PA 2017] 等高线 / Giewont
[PA 2017] 等高线 / Giewont
题目背景
译自 Potyczki Algorytmiczne 2017 R5 Giewont [A] (GIE)。。
题目描述
定义好的多边形为各边平行于一条坐标轴,各个顶点都在整点上的简单多边形。
给定 个好的多边形,这些多边形的边缘两两不交,也不接触。
多边形之间可能相互包含。存在一个多边形包含其他所有的多边形,我们称它为边界。
定义这张图的分数为:选出一个序列 ,使得 ,都有多边形 包含多边形 , 可能的最大值。
在边界内添加若干个好的多边形,使得添加后,这些多边形仍然边缘两两不交,也不接触。最大化添加多边形后的分数,你只需要输出这个分数即可。
可参阅样例解释图片。
输入格式
第一行一个正整数 。
接下来 行描述 个好的多边形:
每行显示一个正偶数 ,然后是 个整数 ,表示第 个多边形的顶点为 $(x_1,x_2),\textcolor{red}{(x_3,x_2)},(x_3,x_4),\textcolor{red}{(x_5,x_4)},\ldots,(x_{k-1},x_k),\textcolor{red}{(x_1,x_k)}$。
按照给定顺序经过多边形的边时,保证多边形的内部在左侧。
给出多边形的顺序是任意的。
输出格式
输出一行一个正整数,表示答案。
6
4 3 5 6 8
8 7 4 9 5 8 6 9 7
4 13 5 14 6
10 8 1 17 12 8 11 0 2 4 0
4 11 4 15 8
4 10 10 13 11
5
提示
样例解释
如下图,实线代表原图中的多边形,虚线代表添加的多边形。
数据范围
- ,;
- 。