#P11809. [PA 2017] 等高线 / Giewont

[PA 2017] 等高线 / Giewont

题目背景

译自 Potyczki Algorytmiczne 2017 R5 Giewont [A] (GIE)。15s,512M\texttt{15s,512M}

题目描述

定义好的多边形为各边平行于一条坐标轴,各个顶点都在整点上的简单多边形。

给定 nn 个好的多边形,这些多边形的边缘两两不交,也不接触。

多边形之间可能相互包含。存在一个多边形包含其他所有的多边形,我们称它为边界

定义这张图的分数为:选出一个序列 a1,a2,,aka_1,a_2,\cdots,a_k,使得 1i<k\forall 1\le i\lt k,都有多边形 aia_i 包含多边形 ai+1a_{i+1}kk 可能的最大值。

在边界内添加若干个好的多边形,使得添加后,这些多边形仍然边缘两两不交,也不接触。最大化添加多边形后的分数,你只需要输出这个分数即可。

可参阅样例解释图片。

输入格式

第一行一个正整数 nn

接下来 nn 行描述 nn 个好的多边形:

每行显示一个正偶数 kk,然后是 kk 个整数 x1,x2,,xkx_1,x_2,\ldots,x_k,表示第 ii 个多边形的顶点为 $(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

提示

样例解释

如下图,实线代表原图中的多边形,虚线代表添加的多边形。

数据范围

  • 2k2\mid kk5×104\sum k\le 5\times 10^4
  • xi108|x_i|\le 10^8