Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
University of Zilina
Matej Bel University in Bansk´ Bystrica
University of West Bohemia
CTU Open Contest 2016
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.
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.
Output for Sample Input