PROBLEM A: UMETNOST RATOVANjA
UVOD:
,,Period zaraćenih država“ (473 – 221. pre nove ere) odnosi se na vekove nemirnih ,,Prolećnih i jesenjih perioda“. Kina je bila podeljena na mnogo manjih država koje su se stalno borile međusobno. Za razliku od prethodnih vekova, kada je viteštvo igralo glavnu ulogu u bitkama i kada su se države uglavnom borile zbog ravnoteže moći ili da reše razmirice, u ovom periodu cilj bitke je bio da se pokore i potpuno unište druge države. Sedam država (Kvi, Ču, Jan, Han, Čao, Vej i Kin), poznatijih kao ,,Sedam moćnih“ igrali su glavnu ulogu. Posle brojnih bitaka, Kin je porazila ostale države, jednu po jednu, stavljajući tako tačku na ,,Period zaraćenih država“.
Zadatak je da se pomoću mape koja pokazuje položaj glavnog grada svake države i granice država označenih kao niz duži, odredi koja se država borila sa kojom. Ako dve države imaju zajedničku granicu, one su ratovale.
ULAZNI PODACI:
Ulaz sadrži nekoliko slučajeva. Svaki slučaj počinje linijom koja sadrži dva broja: broj n (1 ≤ n ≤ 600), broj država i broj m (1 ≤ m ≤ 4000), broj graničnih duži. U sledećih n redova se nalaze koordinate svakog glavnog grada, po dva broja u svakom redu. Zatim su u narednih m redova, m graničnih duži. Svaki od tih redova sadrži četiri cela broja: x1, y1, x2 i y2 koji označavaju da postoji granična duž od (x1, y1) do (x2, y2). (U ulazu nije dato u kakvom su odnosu dve države sa različitih strana granice, ali može se zaključiti iz pravca prostiranja granice.)
Svaka država je obuhvaćena celovitom graničnom linijom. Neke države su okružene pustinjom. Prema tome, granični segment ili deli dve države ili državu od pustinje. Nije moguće da se ista država ili pustinja nalazi sa obe strane granične duži. Može postojati više glavnih gradova u svakoj državi, ali ne postoji glavni grad pustinje. Granične duži se ne ukrštaju i mogu se sresti samo u krajnjim tačkama.
Ulaz se završava naredbom n = m = 0.
IZLAZNI PODACI:
Za svaku situaciju je potrebno ispisati n redova koji opisuju neprijatelje n-te države (setite se da ako dve države dele granicu, oni su neprijatelji). Svaki red počinje brojem x (broj neprijatelja koje data država ima). Zatim sledi x brojeva koji označavaju neprijatelje države. Ovi brojevi su između 1 i n. Broj 1 se odnosi na prvi glavni grad koji se pojavljuje u ulazu, a broj n označava poslednji.
(U ovom primeru se u prvih osam redova ulaz spojio sa izlazom (moja greska izvinjavam se!!!). Dakle u prvih 5 redova se po prva dva broja odnose na ulaz, ostali na izlaz. Slicno, se u naredna 3 reda, prva 4 broja odnose na ulaz, a ostali na izlaz)
PRIMER:
Ulaz: Izlaz:
4 12 2 2 4
3 2 2 1 3
11 8 2 2 4
12 17 2 1 3
1 19 1 2
0 0 10 0 2 1 3
10 0 20 0 2 2 4
20 0 20 10 1 3
20 10 20 20
20 20 10 20
10 20 0 20
0 20 0 10
0 10 0 0
10 0 10 10
0 10 10 10
20 10 10 10
10 20 10 10
4 16
170 13
24 88
152 49
110 130
60 60 140 60
140 60 140 140
140 140 60 140
60 140 60 60
0 0 200 0
200 0 200 200
200 200 0 200
0 200 0 0
40 40 160 40
160 40 160 160
160 160 40 160
40 160 40 40
20 20 180 20
180 20 180 180
180 180 20 180
20 180 20 20
0 0
Okačiću kasnije i probem B,C,D... , ali idemo redom !!!