BIO - Biology


It was no later than 1869 that Jules Verne succeeded to vulgarize interest in the depths of the oceans through his science-fiction novel “Twenty thousand leagues under the sea”. On board the Nautilus manoeuvred by captain Nemo, the crew visits the lost city of Atlantis and gets to know strangest kinds of sea dwellers.

Nearly a century later, one of the deepest points on Earth, the Challenger Deep was visited by Piccard and Walsh and a Swiss flag was dibbled at 10’924 metres below sea level. The ridership of the Trieste submarine was amazed by the animal life in these depths.

 

 

Recently a team of biologists decided to investigate these depths of the Mariana Trench and especially their So Weird Exotic Rare Citizens (SWERC). To this goal a preliminary study was performed, which showed that the species in the Mariana Trench have very local biotopes, which if projected onto the sea surface, can be described by convex polygons. All the biotopes are located at the same depth and some may overlap. The biologists now want to install racks and cameras in each biotope in order to attract and film them. As delicious as the food at the racks might be, no species would ever take the risk to transgress the borders of its habitat. As these cameras and the associated telecommunication system are extremely expensive, their number is to be minimized. Can you tell the biologists for how many cameras they need to account in their budget planning in order not to miss any species if they choose the locations in a clever way? You may consider each camera-rack couple as a mathematical point which must lie strictly inside the biotope in order to attract the related species.

 

INPUT

The input consists of several test-cases separated by an empty line. Each test-case starts with the number of species S (0<=S<=20) . Each of the next S lines describes one biotope. The first entry indicates the number ni  of vertices of the convex polygon. Then follow their coordinates in the order x1 y1 x2 y2 ... xni yni (|xi|,|yi|<=1000). Input terminates on a test-case with S=0, which must not be evaluated.

 

OUTPUT

For each test-case, output the minimum number of camera-rack couples necessary to screen all the species listed in the input.

 

SAMPLE INPUT

3

3 11.00 0.00 -2.50 7.79 -2.50 -7.79

4 4.00 -3.00 -3.00 4.00 -10.00 -3.00 -3.00 -10.00

4 4.00 2.00 3.00 3.00 2.00 2.00 3.00 1.00

 

10

7 -317.00 99.00 -330.55 127.15 -361.01 134.10 -385.43 114.62 -385.43 83.38 -361.01 63.90 -330.55 70.85

6 -99.00 93.00 -238.50 334.62 -517.50 334.62 -657.00 93.00 -517.50 -148.62 -238.50 -148.62

4 113.00 -134.00 42.00 -63.00 -29.00 -134.00 42.00 -205.00

3 90.00 -68.00 -261.00 134.65 -261.00 -270.65

7 218.00 -342.00 147.22 -195.02 -11.83 -158.71 -139.38 -260.43 -139.38 -423.57 -11.83 -525.29 147.22 -488.98

6 131.00 -286.00 38.00 -124.92 -148.00 -124.92 -241.00 -286.00 -148.00 -447.08 38.00 -447.08

4 -170.00 -247.00 -172.00 -245.00 -174.00 -247.00 -172.00 -249.00

4 -332.00 -102.00 -395.00 -39.00 -458.00 -102.00 -395.00 -165.00

6 -52.00 -224.00 -196.50 26.28 -485.50 26.28 -630.00 -224.00 -485.50 -474.28 -196.50 -474.28

5 -101.00 163.00 -210.87 314.22 -388.63 256.46 -388.63 69.54 -210.87 11.78

 

0

 

SAMPLE OUTPUT

2

5

 

    

               Sample input 1                                         Sample input 2


hide comments
[Rampage] Blue.Mary: 2022-09-05 10:43:22

ni <= 40, checked by assertion.

Mateusz Radecki: 2015-05-04 12:45:02

Yea, how large can be N? Can we know limit?

Siarhei Kulik: 2015-05-02 16:34:16

How large is the number of the test cases?

And how large is N? 100000?

Last edit: 2015-05-02 17:14:09
Ashwin: 2012-01-05 22:01:39

@Christian Kauth could I contact you by e-mail, I want to confirm that my approach to the problem is correct

Christian Kauth: 2011-01-10 20:08:57

@Ashwin: Sometimes you use more cameras than needed... you're close!


Added by:Christian Kauth
Date:2010-10-05
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64