[BOJ 8623] Zdjęcia
View as PDFMał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.</p>
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ść.
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.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $n$ ($1 ≤ n ≤ 100\,000$) - jest to liczba zdjęć na tablicy. W każdym z następnych $n$ wierszy znajdują się po cztery liczby całkowite. W wierszu $i+1$-szym zapisane są liczby $L_i$, $D_i$, $P_i$, $G_i$ ($-200\,000 ≤ L_i, D_i, P_i, G_i ≤ 200\,000$ oraz $L_i < P_i$ i $D_i < G_i$), poddzielane pojedynczymi odstępami. Są to współrzędne zdjęcia w układzie kartezjańskim na tablicy: $(L_i, D_i)$ to współrzędne lewego dolnego, natomiast $(P_i, G_i)$ to współrzędne prawego górnego rogu zdjęcia. Przyjmujemy, że pinezka wbita w punkt $(x, y)$ przebije to zdjęcie, jeśli $L_i ≤ x ≤ P_i$ oraz $D_i ≤ y ≤ G_i$.
출력 형식
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.
예제 입력
5
-1 -1 1 2
0 -2 3 0
2 2 3 3
-1 -1 1 2
2 -1 4 1
예제 출력
3
힌트
</p>
Obszar zakreskowany na rysunku reprezentuje fragment tablicy, w którym należy przyczepić pinezkę, aby przebić 3 zdjęcia. Zauważ, że dwa zdjęcia na tablicy (pierwsze i czwarte) dokładnie się pokrywają.
Comments