Fosa [A]
Limit pamięci: 512 MB
Wojska króla Bajtomira podbiły właśnie kolejny skrawek terenu,
jeszcze niedawno należący do królestwa Bitocji.
Jednak aby móc chronić ten teren, należy wybudować warownię.
Poddani króla są bardzo biegli we wznoszeniu dowolnie wielkich konstrukcji
z kamienia i cegły, ale jedno, czego nie cierpią, to kopanie dołów.
A jak wiadomo, każda warownia musi dla bezpieczeństwa zostać otoczona
głęboką fosą.
Na szczęście na podbitym terenie znajduje się całkiem sporo strumieni,
więc nadworny architekt Bajtazar postanowił wykorzystać je jako naturalną fosę.
Zastanawia się teraz, gdzie postawić warownię, żeby z każdej strony
otoczona była strumieniami.
Bajtazar jest miłośnikiem symetrii, więc warownia musi zostać zbudowana
na planie kwadratu.
Ponieważ ma ona pomieścić oddział wojskowy oddelegowany do obrony podbitego
terenu, musi być jak największa.
Królewscy geodeci nanieśli na prostokątną mapę położenie strumieni. Każdy
z nich jest odcinkiem równoległym do jednej z krawędzi mapy.
Odcinki reprezentujące różne strumienie mogą mieć więcej niż jeden
punkt wspólny (tj. płynąć obok siebie w pomijalnej odległości).
Warownię na mapie reprezentować będzie kwadrat.
Musi on zostać tak umieszczony, żeby każdy punkt jego obwodu należał do pewnego
odcinka reprezentującego strumień.
Nie przeszkadza nam, jeśli odcinek reprezentujący strumień będzie
przecinał wnętrze kwadratu (tzn. strumień będzie płynął pod warownią).
Taki strumień można przecież zablokować kratą, a kucharzowi będzie łatwiej karmić
pływające w fosie krokodyle.
Pomóż Bajtazarowi i odpowiedz na pytanie, czy da się zbudować warownię
spełniającą powyższe wymagania. Jeśli tak, to wyznacz również maksymalną długość boku
kwadratu reprezentującego warownię.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (),
oznaczająca liczbę odcinków reprezentujących strumienie na mapie.
Kolejne wierszy zawiera opis poszczególnych odcinków - w -tym
z tych wierszy zapisane są cztery liczby całkowite
(, albo )
oznaczające, że odcinek łączy punkty o współrzędnych i .
Wyjście
W jedynym wierszu wyjścia należy zapisać słowo NIE, jeśli nie da
się zbudować warowni zgodnie z wymogami architekta.
W przeciwnym wypadku należy wypisać jedną dodatnią liczbę całkowitą, oznaczającą
największą długość boku kwadratu reprezentującego warownię.
Przykład
Dla danych wejściowych:
6
-1 0 2 0
0 2 3 2
0 -1 0 2
2 0 2 3
1 1 1 3
2 3 1 3
poprawną odpowiedzią jest:
2
Autor zadania: Jakub Łącki.