Mam takie zadanie:
Zdjęcia
Limit pamięci: 32 MB
Mały Bajtek na swoje siódme urodziny dostał od rodziców aparat fotograficzny. Od tego czasu uwielbia robić zdjęcia każdej nowo poznanej osobie. Każde zdjęcie, które zrobi, wywiesza na tablicy korkowej w swoim pokoju. Od urodzin minęło parę miesięcy i tablica jest już mocno zapełniona. Niektóre zdjęcia są całkowicie zasłonięte, inne częściowo... Jeszcze inne, najnowsze, są widoczne w całości.
Kiedy Bajtek przyczepia nowe zdjęcia pinezkami, zastanawia się, ile spośród dotychczas wywieszonych zdjęć przebija każda z nowych pinezek. Chłopiec jest ciekaw, ile zdjęć może maksymalnie przebić jedna taka pinezka. Pomóż Bajtkowi zaspokoić ciekawość.
Zadanie
Napisz program, który
- wczyta ze standardowego wejścia opis zdjęć znajdujących się na tablicy korkowej Bajtka,
- wyznaczy maksymalną liczbę zdjęć, które może przebić pinezka wbita w tablicę,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () - jest to liczba zdjęć na tablicy. W każdym z następnych wierszy znajdują się po cztery liczby całkowite. W wierszu -szym zapisane są liczby , , , ( oraz i ), poddzielane pojedynczymi odstępami. Są to współrzędne zdjęcia w układzie kartezjańskim na tablicy: to współrzędne lewego dolnego, natomiast to współrzędne prawego górnego rogu zdjęcia. Przyjmujemy, że pinezka wbita w punkt przebije to zdjęcie, jeśli oraz .
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą - maksymalną liczbę zdjęć, które może przebić pinezka wbita w pewnym miejscu tablicy.
Przykład
Dla danych wejściowych:
5
-1 -1 1 2
0 -2 3 0
2 2 3 3
-1 -1 1 2
2 -1 4 1
poprawną odpowiedzią jest:
3
Wydaje mi się że trzeba jakoś użyć drzewa i kolejkę priorytetową, mógłby mi ktoś pomóc to rozwiązać?