#P17763. luotianyi
luotianyi
题目描述
在「无限共鸣 · 流光协奏」演唱会上,洛天依想要配合地面的水波效果完成一场盛大的演出。洛天依可以站在舞台的任意一处,环绕着她的水波层层环绕,音浪也随水波舞动。
由于场地限制,所有的水波都是一个多边形。若把舞台抽象为平面直角坐标系,每条水波都是一条闭合简单折线,其所有顶点坐标都是整数,且每条边都平行于某一条坐标轴。
现在,舞台上已经策划好了 条水波的位置,保证它们两两不相交,也不接触。水波之间可以互相包含,并保证存在一条水波包含所有其它水波,其为水波的边缘。这里,我们称一条水波 包含另一条水波 ,当且仅当 表示的多边形包含的点集为 对应的子集。
之后,洛天依会选择水波边缘内的一个位置(不一定是整点)进行表演,音浪穿过一层水波就是一次共鸣。这次表演的共鸣值为最大的正整数 (k),使得存在水波序列 (a_1,a_2,\ldots,a_k),满足对所有 (1\le i<k),水波 (a_i) 包含水波 (a_{i+1}),且洛天依的位置位于水波 (a_k) 围成区域的严格内部。
为了契合这次的主题「无限共鸣」,她想要使得共鸣值 的值尽量大。有时,为了更好的演出效果,她可以在舞台上绘制任意条位于水波边缘之内的水波,在添加完这些水波后,舞台上的水波仍然需要满足上述条件,即:
- 每条水波一条闭合简单折线,其所有顶点坐标都是整数,且每条边都平行于某一条坐标轴;
- 任意两条不同的水波都不相交或接触。
此时,她想要求出在添加水波过后共鸣值 的最大值。输入将会给定参数 ,当 你需要求出洛天依不能绘制新的水波时的答案,当 时你需要求出洛天依可以绘制新的水波时的答案。
输入格式
本题有多组测试数据。输入的第一行两个整数 表示测试点编号和测试数据组数,特别的,在样例输入中,。
对于每组测试数据:
第一行两个整数 ,表示已有舞台上已有的水波数量和询问类型。
接下来 行描述 条水波,其中第 行首先给出一个正整数 ,表示这条水波的顶点数。随后给出 个整数 ,并令 ,则这条水波的第 个顶点为:
- 若 为奇数,则第 个顶点为 ;
- 若 为偶数,则第 个顶点为 。
保证由此还原出的多边形顶点按逆时针顺序给出。
输出格式
对于每组测试数据,输出一行一个整数表示对应 的答案。
样例
样例 1
0 1
3 0
4 0 0 14 12
8 2 2 12 10 8 8 4 10
6 5 3 10 7 8 5
3
样例解释 1
输入中 ,不能绘制新的水波。图中蓝色为输入中给出的水波,红点表示某最优答案中洛天依的位置。

_样例 2
0 1
2 1
8 0 0 20 18 14 12 6 18
6 2 13 5 16 4 14
6
样例解释 2
输入中 ,可以绘制新的水波。图中蓝色为输入中给出的水波,红点表示某最优答案中洛天依的位置,橙色为此时洛天依绘制的额外水波。

数据范围与提示
设 为单个测试点内所有测试数据中多边形顶点数量之和的最大值, 为输入的 的绝对值的最大值。对于所有测试数据:
- ;
- ;
- ;
- 对于输入的所有水波, 均为大于 的偶数;
- ;
- ;
- 保证输入符合题目所述全部条件。
| 测试点编号 | 特殊性质 | |||
|---|---|---|---|---|
| 无 | ||||
| A | ||||
| 无 | ||||
| B | ||||
| C | ||||
| 无 | ||||
| D | ||||
| 无 | ||||
| A | ||||
| B | ||||
| C | ||||
| 无 | ||||
| A | ||||
| D | ||||
| 无 |
- 特殊性质 A:保证输入的水波均有 ,即其对应的多边形为矩形;
- 特殊性质 B:保证存在排列 使得保证所有水波的之间包含关系形成一条链;
- 特殊性质 C:保证所有非边缘水波两两互不包含;
- 特殊性质 D:保证输入的水波均有 。