Plemiona [B]
Limit pamięci: 384 MB
UWAGA: Na prawdziwych zawodach limit pamięci wynosił 1024 MB.
Profesor Bajtowicz jest cieszącym się wielkim uznaniem historykiem.
Ostatnio opracował śmiałą hipotezę, wyjaśniającą proces
formowania się pierwszych państw na kontynencie Bajtopii.
Powszechnie wiadomo, że zaraz po wielkiej wędrówce ludów tereny
te zamieszkiwało plemion. Co ciekawe, każde z plemion zajmowało
pewne terytorium, które na mapie Bajtopii jest prostokątem o bokach równoległych do
boków mapy. Terytoria nie musiały być rozłączne,
wobec tego na niektórych terenach dochodziło do spotkania kilku kultur.
W myśl hipotezy profesora Bajtowicza, jeżeli tylko przecięcie
terytoriów dwóch plemion miało dodatnie pole, to po pewnym czasie te plemiona
łączyły się. Dawało to bodziec do dalszej ekspansji i nowo powstałe plemię
rozprzestrzeniało się wewnątrz najmniejszego prostokąta (o bokach
równoległych do boków mapy) zawierającego oba ich dotychczasowe terytoria.
Profesor Bajtowicz twierdzi, że proces ten zachodził nieprzerwanie, aż
w pewnym momencie przecięcie każdej pary terytoriów miało zerowe pole.
Wtedy sytuacja ustabilizowała się i obszary zajmowane przez plemiona
przekształciły się w pierwsze państwa.
Profesor wie, że nawet jego autorytet może nie wystarczyć,
aby tak innowatorska hipoteza została przyjęta przez skostniałe
środowisko naukowe. Na szczęście, dzięki swoim poprzednim badaniom, dysponuje
on dwiema dokładnymi mapami.
Jedna z nich opisuje lokalizacje pierwotnych plemion, zaś druga -
pierwszych państw. Bajtowicz zatrudnił Cię potajemnie, abyś przeprowadził
(na podstawie pierwszej mapy)
symulację rozwoju plemion według jego modelu. Kiedy dostarczysz mu teoretyczne
wyniki, porówna je z faktycznym rozmieszczeniem państw na drugiej mapie
i stwierdzi, czy jego hipoteza ma szanse być prawdziwa.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę pierwotnych plemion zamieszkujących Bajtopię.
Następne wierszy zawiera po cztery liczby całkowite , , oraz ,
, oznaczające,
że pewne plemię zamieszkiwało terytorium, które na mapie jest prostokątem, którego dwa przeciwległe wierzchołki to oraz .
Wyjście
Twój program powinien wypisać w pierwszym wierszu jedną liczbę całkowitą
, oznaczającą liczbę państw, które powinny powstać według hipotezy Bajtowicza.
Następnie Twój program powinien wypisać wierszy, a w każdym
z nich cztery liczby całkowite , , i pooddzielane pojedynczymi odstępami,
oznaczające, że terytorium jednego z państw jest na mapie prostokątem o przeciwległych wierzchołkach
oraz , przy czym , .
Czwórki te muszą być różne oraz powinny zostać wypisane w kolejności leksykograficznej.
Przykład
Dla danych wejściowych:
5
7 8 1 4
1 5 2 3
4 5 2 7
2 3 5 9
4 6 8 9
poprawną odpowiedzią jest:
2
1 6 2 9
7 8 1 4
Autor zadania: Bartosz Tarnawski.