V Olimpiada Informatyczna 1997/98
|
Zadanie: OKN
|
Autor: Wojciech Guzicki
|
II ETAP, DRUGI DZIEŃ ZAWODÓW - SOBOTA 14 LUTEGO 1998 r. |
Plik źródłowy: | OKN.??? (np. pas, c, cpp) |
Plik wykonywalny: | OKN.exe |
Plik wejściowy: | OKN.in |
Plik wyjściowy: | OKN.out |
W prostokątnym układzie współrzędnych dany jest wielokąt o bokach równoległych do osi układu. Każde dwa kolejne boki w tym wielokącie są do siebie prostopadłe, a każdy wierzchołek ma współrzędne całkowitoliczbowe. Dane jest również okno, czyli prostokąt o bokach równoległych do osi układu. Wnętrze wielokąta (ale nie jego brzeg) zostało pokolorowane na czerwono. Jaka jest liczba rozłącznych czerwonych fragmentów wielokąta widzianych przez okno?
Przyjrzyjmy się rysunkowi poniżej:
Napisz program, który:
W pierwszym wierszu pliku wejściowego OKN.IN znajdują się cztery liczby całkowite x1, y1, x2, y2 z przedziału [0..10000] oddzielone pojedynczymi odstępami. Liczby x1, y1 są współrzędnymi górnego-lewego rogu okna. Liczby x2, y2 są współrzędnymi dolnego-prawego rogu okna. Następny wiersz pliku wejściowego zawiera liczbę całkowitą n, 4<=n<=5000. Jest to liczba wierzchołków wielokąta. W kolejnych n wierszach znajdują się współrzędne kolejnych wierzchołków wielokąta danych w kierunku przeciwnym do ruchu wskazówek zegara, tzn. wnętrze wielokąta leży po lewej stronie jego brzegu, gdy przesuwamy się wzdłuż boków wielokąta zgodnie z zadanym porządkiem. Każdy wiersz zawiera dwie liczby całkowite x, y oddzielone pojedynczym odstępem, 0<=x<=10000, 0<=y<=10000. Liczby w wierszu i + 2, 1<=i<=n, w pliku OKN.IN są współrzędnymi i-tego wierzchołka wielokąta.
Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego OKN.OUT jedną liczbę całkowitą, a mianowicie - liczbę rozłącznych czerwonych fragmentów wielokąta widzianych przez okno.
Dla pliku wejściowego OKN.IN:
0 5 8 1 24 0 0 4 0 4 2 5 2 5 0 7 0 7 3 3 3 3 2 2 2 2 4 1 4 1 5 2 5 2 6 3 6 3 5 4 5 4 6 5 6 5 4 7 4 7 7 0 7poprawnym rozwiązaniem jest plik wyjściowy OKN.OUT :
2