V Olimpiada Informatyczna 1997/98

Zadanie: PRO
Autor: Wojciech Guzicki
Prostokšty

III ETAP, DRUGI DZIEŃ ZAWODÓW - ŒRODA 8 KWIETNIA 1998 r.  
Plik źródłowy: PRO.??? (np. pas, c, cpp)
Plik wykonywalny: PRO.exe
Plik wejściowy: PRO.in
Plik wyjściowy: PRO.out

Na płaszczyźnie narysowano n prostokątów, których boki są równoległe do osi współrzędnych i wierzchołki mają obie współrzędne całkowite.
Przyjmujemy że:

Przykłady

Prostokąty na rysunku a tworzą dwa rozłączne bloki.

Rysunek a

[Rysunek a]

Prostokąty na rysunku b tworzą jeden blok.

Rysunek b
[Rysunek b]

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku wejściowego PRO.IN znajduje się liczba całkowita n, 1 <= n <= 7000. Jest to liczba prostokątów. W następnych n wierszach są zapisane współrzędne wierzchołków prostokątów. Każdy prostokąt jest opisany za pomocą czterech liczb: współrzędnych x i y lewego dolnego wierzchołka oraz współrzędnych x i y prawego górnego wierzchołka. Są to liczby całkowite nieujemne nie większe niż 10000.

Wyjście

W pierwszym i jedynym wierszu pliku PRO.OUT należy zapisać jedną liczbę całkowitą: liczbę rozłącznych bloków utworzonych przez dane prostokąty.

Przykład

Dla pliku tekstowego PRO.IN:

9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1
poprawnym rozwiązaniem jest plik wyjściowy PRO.OUT:
2

Twój program powinien szukać pliku PRO.IN w katalogu bieżącym i tworzyć plik PRO.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę PRO.??? gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku PRO.EXE.