Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2016

Aerial Archeology

archeology.c, archeology.cpp, archeology.c11, Archeology.java, archeology.py

Andrew is on a summer vacation job with a group of aerial archeologists. The group is inter-

nationally 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 he-

licopter 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.

Input Specification

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.

Output Specification

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.

Sample Input

3

4

00

01

11

10

4

12

13

23

22

5

21

22

92

10 3

10 1

Output for Sample Input

2