#P17763. luotianyi

luotianyi

题目描述

在「无限共鸣 · 流光协奏」演唱会上,洛天依想要配合地面的水波效果完成一场盛大的演出。洛天依可以站在舞台的任意一处,环绕着她的水波层层环绕,音浪也随水波舞动。

由于场地限制,所有的水波都是一个多边形。若把舞台抽象为平面直角坐标系,每条水波都是一条闭合简单折线,其所有顶点坐标都是整数,且每条边都平行于某一条坐标轴。

现在,舞台上已经策划好了 nn 条水波的位置,保证它们两两不相交,也不接触。水波之间可以互相包含,并保证存在一条水波包含所有其它水波,其为水波的边缘。这里,我们称一条水波 aa 包含另一条水波 bb,当且仅当 bb 表示的多边形包含的点集为 aa 对应的子集。

之后,洛天依会选择水波边缘内的一个位置(不一定是整点)进行表演,音浪穿过一层水波就是一次共鸣。这次表演的共鸣值为最大的正整数 (k),使得存在水波序列 (a_1,a_2,\ldots,a_k),满足对所有 (1\le i<k),水波 (a_i) 包含水波 (a_{i+1}),且洛天依的位置位于水波 (a_k) 围成区域的严格内部。

为了契合这次的主题「无限共鸣」,她想要使得共鸣值 kk 的值尽量大。有时,为了更好的演出效果,她可以在舞台上绘制任意条位于水波边缘之内的水波,在添加完这些水波后,舞台上的水波仍然需要满足上述条件,即:

  • 每条水波一条闭合简单折线,其所有顶点坐标都是整数,且每条边都平行于某一条坐标轴;
  • 任意两条不同的水波都不相交或接触。

此时,她想要求出在添加水波过后共鸣值 kk 的最大值。输入将会给定参数 pp,当 p=0p=0 你需要求出洛天依不能绘制新的水波时的答案,当 p=1p=1 时你需要求出洛天依可以绘制新的水波时的答案。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据:

第一行两个整数 n,pn,p,表示已有舞台上已有的水波数量和询问类型。

接下来 nn 行描述 nn 条水波,其中第 i(1≤i≤n)i(1\le i\le n) 行首先给出一个正整数 kk,表示这条水波的顶点数。随后给出 kk 个整数 a1,a2,⋯ ,aka_1,a_2,\cdots,a_k,并令 ak+1=a1a_{k+1}=a_1,则这条水波的第 ii 个顶点为:

  • 若 ii 为奇数,则第 ii 个顶点为 (ai,ai+1)(a_i,a_{i+1});
  • 若 ii 为偶数,则第 ii 个顶点为 (ai+1,ai)(a_{i+1},a_i)。

保证由此还原出的多边形顶点按逆时针顺序给出。

输出格式

对于每组测试数据,输出一行一个整数表示对应 pp 的答案。

样例

样例 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

输入中 p=0p=0,不能绘制新的水波。图中蓝色为输入中给出的水波,红点表示某最优答案中洛天依的位置。

_样例 2

0 1
2 1
8 0 0 20 18 14 12 6 18
6 2 13 5 16 4 14
6

样例解释 2

输入中 p=1p=1,可以绘制新的水波。图中蓝色为输入中给出的水波,红点表示某最优答案中洛天依的位置,橙色为此时洛天依绘制的额外水波。

数据范围与提示

设 max⁡∑k\max\sum k 为单个测试点内所有测试数据中多边形顶点数量之和的最大值,max⁡∣ai∣\max |a_i| 为输入的 aia_i 的绝对值的最大值。对于所有测试数据:

  • 1≤T≤51\le T\le 5;
  • 1≤n≤2.5×1041\le n\le 2.5\times 10^4;
  • p∈{0,1}p\in\{0,1\};
  • 对于输入的所有水波,kk 均为大于 22 的偶数;
  • max⁡∑k≤105\max\sum k\le 10^5;
  • max⁡∣ai∣≤108\max|a_i|\le 10^8;
  • 保证输入符合题目所述全部条件。
测试点编号 n≤n\le max⁡∑k≤\max\sum k\le p=p= 特殊性质
11 33 2020 00 无
22 2020 200200
33 100100 20002000
44 500500 10410^4
55 5×1035\times 10^3 2.5×1042.5\times 10^4
66 10410^4 4×1044\times10^4
77 1.75×1041.75\times 10^4 7.5×1047.5\times10^4
88 2.5×1042.5\times 10^4 10510^5 A
99 无
1010 11 1010 11
1111 2020 200200
1212 100100 20002000
1313 500500 10410^4
1414 2×1032\times 10^3 1.5×1041.5\times 10^4 B
1515 C
1616 5×1035\times 10^3 2.5×1042.5\times 10^4 无
1717 10410^4 4×1044\times10^4 D
1818 无
1919 1.5×1041.5\times 10^4 6×1046\times10^4 A
2020 B
2121 C
2222 1.75×1041.75\times 10^4 7.5×1047.5\times10^4 无
2323 2.5×1042.5\times 10^4 10510^5 A
2424 D
2525 无
  • 特殊性质 A:保证输入的水波均有 k=4k=4,即其对应的多边形为矩形;
  • 特殊性质 B:保证存在排列 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n 使得保证所有水波的之间包含关系形成一条链;
  • 特殊性质 C:保证所有非边缘水波两两互不包含;
  • 特殊性质 D:保证输入的水波均有 k≤10k\le 10。