Kontynent

23.11.2011

Kontynent

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Kornelia jest bardzo ciekawa otaczającego ją świata. Chłonie wiedzę w takim tempie, że nie wystarczają jej już nawet dodatkowe zajęcia w przedszkolu. Wieczorami otwiera swoją ulubioną "Geografię dla najmłodszych" i poznaje obce kraje z odległych kontynentów.

Każdy rozdział książki opowiada o jednym kontynencie, którego mapa polityczna znajduje się na pierwszej stronie rozdziału. Właściwie "znajduje się" to za dużo powiedziane - trzeba ją bowiem odtworzyć samemu. Na marginesie strony podane są współrzędne wszystkich odcinków tworzących granice państw na danym kontynencie. Zadaniem naszej bohaterki jest nanieść je na mapę i pokolorować poszczególne kraje - każdy innym kolorem. Kornelia zastanawia się, jak wielu różnych kredek będzie potrzebować oraz jak duże powierzchnie będzie musiała kolorować każdą z nich. Poprosiła więc o pomoc Ciebie jako zaufanego kolegę swojego brata, Hektora.

Wejście

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii pojedynczego zestawu testowego znajduje się jedna liczba całkowita N ( 3 <= N <= 8 000 ), określająca liczbę odcinków reprezentujących granice państw kontynentu. Każda z kolejnych N linii zawiera cztery liczby całkowite x1, y1, x2, y2 ( 0 <= x1, y1, x2, y2 <= 10 000 ) oznaczająca odcinek o końcach w punktach (x1,y1) i (x2,y2).

Każdy z odcinków ma niezerową długość i reprezentuje fragment granicy między dokładnie dwoma różnymi państwami, lub fragment granicy państwa na krawędzi kontynentu/mapy. Żadne dwa odcinki nie przecinają się, a co najwyżej stykają się końcami. Każde z państw ma kształt wielokąta prostego bez dziur.

Wyjście

Dla każdego zestawu testowego należy w pierwszej linii wypisać liczbę P państw na kontynencie podanym na wejściu. W następnej linii należy wypisać dokładnie P liczb oddzielonych pojedynczą spacją, oznaczające pola wielokątów reprezentujących państwa. Pola te powinny być uszeregowane w kolejności niemalejącej i wypisane z dokładnością dokładnie jednego miejsca po przecinku.

Przykład

Wejście Wyjście

2
5
0 0 1 0
1 0 1 1
1 1 0 1
0 0 0 1
1 1 0 0
12
1 1 1 4
0 0 4 0
6 3 4 0
4 1 6 3
2 1 4 1
2 1 0 0
3 2 2 1
4 1 4 0
2 1 1 1
1 4 6 3
4 1 3 2
0 0 1 4

2
0.5 0.5
5
1.0 1.0 2.0 3.0 9.5

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com