





Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Rolnik Bitek analizuje zdjęcia satelitarne swojego pola. Jego pole można reprezentować jako dwuwymiarowy układ współrzędnych. Z darmowych dostępnych internetowych źródeł udało mu się znaleźć N zdjęć, każde w kształcie prostokąta o dwóch naprzeciwległych wierzchołkach w punktach xi, 1, yi, 1 oraz xi, 2, yi, 2.
Bitkowi zależało na tym, żeby zdjęcia coraz lepiej przybliżały konkretny obszar jego pola. Innymi słowy chciałby, żeby zdjęcia dało posegregować się w takiej kolejności, że każde następne zdjęcie jest pewną częścią poprzedniego. Formalnie, jedno zdjęcie jest pewną częścią innego zdjęcia, jeżeli prostokątny obszar zawarty na pierwszym zdjęciu w całości zawiera się w prostokątnym obszarze drugiego zdjęcia.
Niestety, Bitek nie jest pewien, czy takie ułożenie zdjęć jest w ogóle możliwe. Pomóż mu i napisz program, który odpowie na jego pytanie.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę znalezionych przez Bitka zdjęć. W następnych N wierszach następuje opis zdjęć. i-ty opis składa się z czterech liczb całkowitych xi, 1, yi, 1 oraz xi, 2, yi, 2, oznaczających pewne dwa naprzeciwległe wierzchołki prostokątnego obszaru pola Bitka zawartego na i-tym zdjęciu satelitarnym.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać słowo
TAK
, jeżeli zdjęcia da się posegregować wg wymagań Bitka,
lub słowo NIE
jeżeli nie jest to możliwe.
Ograniczenia
1 ≤ N ≤ 200 000, 0 ≤ xi, j, yi, j ≤ 109, xi, 1 ≠ xi, 2 oraz yi, 1 ≠ yi, 2 dla i = 1, …, N, j = 1, 2.
Przykład
Wejście | Wyjście | |
|
|
Wejście | Wyjście | |
|
|