13914번 - Aerial Archeology 다국어

Andrew is on a summer vacation job with a group of aerial archeologists. The group is internationally known for their advances in using nuclear imaging spectroscopy to investigate the underground remains of prehistoric cultures. Today, Andrew’s job is to find a route for a helicopter which will carry the spectrometer over the area of archeological interest in the nearby lowlands. The spectrometer is a very sensitive and vulnerable device and the helicopter carrying it has to fly at constant speed in a perfectly straight line to minimize the measurement noise.

Hidden under the surface in the lowlands, there are more prehistoric settlements whose location and boundaries have been previously established by other techniques. All settlement boundaries are drawn on a special map which is at Andrew’s disposal. The goal of the flight is to fly over as many settlements as possible and measure the soil composition in and around them. Thus, all Andrew has to do is to draw such straight line on the map that intersects the maximum number of settlements drawn there.

The shapes of the settlements are complicated and the settlements overlap, often chaotically. So it is not immediately obvious where to draw the line.

The input describes the shapes and the positions of settlements on the map. Each settlement is represented as a simple polygon (no two of its non-adjacent boundary segments touch or intersect each other). The polygons may overlap one another.

There are more test cases in the input. Each case starts with a line containing one positive integer N which specifies the number of polygons on the map. Then there is the description of N polygons. Each polygon description starts with one text line containing single integer M (M ≥ 3) which denotes the number of vertices of the polygon. The next M lines specify the vertices of the polygon. Each of these lines specifies one vertex by its two coordinates x, y separated by space. The vertices are listed in the clockwise direction along the polygon boundary. All coordinates are integers with an absolute value at most 10 000. The total number of vertices of all polygons on the map does not exceed 1 000.

For each test case, print a single line with integer P denoting the maximum number of polygons on the map which can be intersected by a straight line. Note that only the intersections of the line with the interior of the polygons are considered.