P4633 [POI 2004] WYS

题目背景

虽然题目名比较毒瘤,但这确实是一个简单题。

题目描述

给 $n$ 个互不相交的多边形,这些多边形的边均平行或垂直于坐标轴。定义多边形 $i$ 的深度 $d_i$ 为 $\max\{d_j\}+1$,其中多边形 $j$ 包含多边形 $i$。特别的,若一个多边形不被任何多边形包含,则其深度为 $1$。求深度最大的多边形的深度。

输入格式

第一行一个正整数 $n$。 接下来每行描述一个多边形。首先给出一个偶数 $k$ $(4 \leqslant k \leqslant 10000)$,接下来包含 $k$ 个整数: $x_1,x_2,\cdots,x_k$ $(0 \leqslant x_i \leqslant 10^8)$。这些点的坐标分别为 $(x_1, x_2), (x_3, x2), (x_3, x4), (x_5, x_4),\cdots,(x_{k-1}, x_k), (x_1, x_k)$。他们按照逆时针顺序构成多边形。

输出格式

输出一个整数表示最大深度。

说明/提示

对于 $100\%$ 的数据,$n \leqslant 40000, \sum k \leqslant 200000$。