408948: GYM103388 F Freedom from Prison

Michael and his brother Lincoln are unfairly imprisoned in the same prison, but Michael has a plan to rescue his brother. The prison can be seen as a set of convex polygons in the plane, in which the edges of the polygons are walls. The walls of distinct polygons do not intersect, but polygons may be nested, that is, inside one another. Michael and Lincoln can be seen as two points in the plane. The rescue path will be for Michael to reach his brother and then both of them need to escape the prison.

Walking for them is no problem, but climbing walls is dangerous and difficult, so Michael will try to minimize the total number of walls climbed by him. So Michael first needs to climb some walls to reach his brother if they are not within the same area and then climb some more walls to leave the prison. Leaving the prison means not being within any walls, which can be seen as reaching a point very far away, let's say $$$(10^{20},10^{20})$$$. Brad is in charge of the placements of the prisoners and is aware of the plan, so he will place both prisoners in two different points in the plane not contained by any segments and such that the minimum amount of walls that need to be climbed by Michael is maximum. What is the minimum amount of walls to be climbed if Brad places the brothers optimally?

Illustration for valid placement in Example 1. Point M represents Michael and point L represents Lincoln

Illustration for valid placement in Example 2

The first line of the input contains one integer $$$N$$$ ($$$1 \le N \le 2 \times 10^5$$$), the number of convex polygons. This line is followed by the descriptions of each polygon. The $$$i$$$-th description starts with an integer $$$k_i$$$ ($$$3 \le k_i \le 6 \times 10^5$$$) followed by $$$k_i$$$ lines, each line contains a point ($$$x_j$$$, $$$y_j$$$) ($$$-10^{9} \le x_j,y_j \le 10^{9}$$$).

The points in the order they are given form a convex polygon in counter-clockwise order and no three consecutive points from the polygon are collinear. No two edges from different polygons intersect. The total number of edges does not exceed $$$6 \times 10^5$$$, that is $$$\sum_{i=1}^{N}k_i \leq 6 \times 10^5$$$.

Print one integer, the minimum number of walls that need to be climbed by Michael to rescue his brother, supposing that Brad assigned the brothers places so that such number of walls is maximum.

4
4
1 10
-2 13
-5 7
-1 6
5
15 11
9 20
-6 19
-14 5
5 0
4
-1 15
-8 7
1 4
2 11
3
7 17
7 6
12 11

6

2
4
0 0
3 0
3 3
0 3
4
1 1
2 1
2 2
1 2

4