Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LIBRARY2 - Biblioteka - Korytarze

Biblioteka Kasi zaczęła się doskonale rozwijać. Zarobione pieniądze postanowiono wydać na remont starego budynku. Podczas prac budowlanych robotnicy odkryli, że w piwnicy znajduje się dziura prowadząca do sieci podziemnych korytarzy, o których krążyły w mieście liczne opowieści. Dzięki nim wiadomo, że wszystkie ściany są do siebie prostopadłe lub równoległe i nie ma nigdzie takiego miejsca w którym korytarze otaczałyby grunt z 4 stron. 

Opierając się na tych założeniach, zdolni budowlańcy postanowili skonstruować robota, który porusza się cały czas wzdłuż ściany i zbiera cenne informacje o budowie sieci korytarzy. Robot wysyła wiadomość do robotników zawierającą jego pozycję zawsze gdy napotyka róg ściany, czyli wtedy kiedy musi zmienić kierunek w którym się porusza. Napisz program, który na podstawie wszystkich zebranych wiadomości pomoże ustalić jaka jest szerokość tych korytarzy w najwęższym miejscu.

Wejście:

W pierwszym wierszu znajduje się liczba naturalna N (N < 500 001) oznaczająca ilość wiadomości wysłanych robotnikom. W każdym z kolejnych N wierszy znajdują się dwie liczby całkowite A i B (- 1 000 001 < A,B < 1 000 001) oznaczające współrzędne robota podane w i-tej wiadomości (robot rozpoczyna/kończy pracę w punkcie o współrzędnych (0;0) i nie wysyła wtedy wiadomości).

Wyjście:

Na standardowe wyście wypisz jedną liczbę naturalną W, będącą szerokością najwęższego tunelu.

Przykład:

Wejście:  (obrazek poglądowy)
11
11 3 0 3 4 4 4 4 0 4 -4 6 -4 6 7 -5 7 -5 -5 -4 -5 -4 0
-4 0

Wyjście:
1

 


Dodane przez:Jakub Pierewoj
Data dodania:2011-07-21
Limit czasu wykonania programu:0.119s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.