P4633 [POI 2004] WYS

Although the title is a bit nasty, this is indeed a simple problem.

You are given $n$ pairwise disjoint polygons. All edges of these polygons are parallel or perpendicular to the coordinate axes. Define the depth $d_i$ of polygon $i$ as $\max\{d_j\}+1$, where polygon $j$ contains polygon $i$. In particular, if a polygon is not contained in any other polygon, then its depth is $1$. Find the depth of the polygon with the maximum depth.

The first line contains a positive integer $n$. Each of the following lines describes one polygon. First, an even integer $k$ $(4 \leqslant k \leqslant 10000)$ is given, followed by $k$ integers: $x_1,x_2,\cdots,x_k$ $(0 \leqslant x_i \leqslant 10^8)$. The coordinates of the points are $(x_1, x_2), (x_3, x_2), (x_3, x_4), (x_5, x_4),\cdots,(x_{k-1}, x_k), (x_1, x_k)$. They form the polygon in counterclockwise order.

Output one integer, the maximum depth.

For $100\%$ of the testdata, $n \leqslant 40000, \sum k \leqslant 200000$. Translated by ChatGPT 5