Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ077 - PTwPZ Atlas

Atlas

Treść

Członkowie Koła Naukowego Wydziału Informatyki po wielu sukcesach w międzynarodowych konkursach programistycznych nie spoczywają na laurach i przygotowują się do następnych. Tym razem postanowili zrealizować multimedialny interaktywny atlas świata. Oprócz wielu innowacji, takich jak prognozowanie wędrówki kontynentów czy symulacja efektu motyla, oprogramowanie będzie zawierać wszystkie charakterystyczne dla tego typu projektów funkcjonalności.

Jedną z nich jest polityczna mapa świata. Aby móc ją poprawnie wygenerować nasi programiści potrzebują informacji o sąsiedztwie poszczególnych państw. Możesz im pomóc pisząc moduł, który będzie podawał takie informacje. Dla zbioru państw opisanych jako wielokąty wyznacz liczbę sąsiadów każdego z nich. Dla ułatwienia pisania pierwszej wersji możesz przyjąć, że na mapie nie występują enklawy, a każdy z krajów jest podany jako pojedynczy wielokąt.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych znajduje się liczba państw n (1<=n<=10000). Dalej podane są opisy poszczególnych państw.

Pierwszy wiersz takiego opisu zawiera liczbę wierzchołków mi (3<=mi<=100000) opisujących granicę i-tego państwa. W kolejnych mi wierszach znajdują się po dwie liczby całkowite xj i yj (0<=xj,yj<=109), oddzielone pojedynczą spacją, definiujące położenie j-tego wierzchołka w kartezjańskim układzie współrzędnych. Po połączeniu kolejnych wierzchołków, oraz ostatniego z pierwszym, otrzymamy nieprzecinające się odcinki definiujące granicę i-tego państwa.

Można założyć, że dane wejściowe zawsze reprezentują poprawną mapę, a sumaryczna liczba wierzchołków nie przekracza 100000. Oprócz tego żadna para odcinków nie pokrywa się częściowo. Dowolne dwa odcinki mogą być całkowicie rozłączne, stykać się w jednym z końców lub całkowicie się pokrywać.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg liczb całkowitych oznaczających liczbę sąsiadów kolejnych państw podanych na wejściu. Każdy element tego ciągu powinien być wypisany w osobnym wierszu. Należy przyjąć, że dwa państwa sąsiadują ze sobą wtedy i tylko wtedy, gdy istnieje co najmniej jeden wspólny odcinek ich granic.

Przykład

dane wejściowe:
1
4
4
0 2
2 2
2 4
0 4
3
2 4
0 4
1 5
3
0 2
2 2
1 1
3
2 2
4 2
3 1

wynik:
2
1
1
0


Dodane przez:Michael Suchacz
Data dodania:2009-07-26
Limit czasu wykonania programu:0.267s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.