Polish version    English version  
  Historia OI -> V OI 1997/1998 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Terminarz
Statystyki
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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:

  • każdy prostokąt jest blokiem,
  • jeśli dwa różne bloki mają wspólny odcinek to tworzą one nowy blok, w przeciwnym przypadku mówimy, że są rozłączne.

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:

  • wczytuje z pliku tekstowego PRO.IN liczbę prostokątów oraz współrzędne ich wierzchołków;
  • znajduje liczbę rozłącznych bloków utworzonych przez te prostokąty;
  • zapisuje wynik w pliku tekstowym PRO.OUT.

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.





Wersja do druku