Problem description


Przekaźniki
(przekazniki)
Limit pamięci: 512 MB
Limit czasu: 6.00 s

Firma telekomunikacyjna JANUSZKOM postanowiła rozstawić N przekaźników radiowych wzdłuż kraju. Przekaźniki ustawione będą na jednej prostej. Dla każdego z przekaźników wyznaczone zostały dwie możliwe współrzędne, na którym powinien znaleźć się dany przekaźnik. Dla każdego z przekaźników należy wybrać jedną z tych współrzędnych. Ponadto chcielibyśmy, żeby przekaźniki zostały rozstawione możliwie równomiernie. Formalnie, chcielibyśmy, żeby minimalna odległość między pewną parą przekaźników była największa możliwa.

Oczywiście to zadanie zostało powierzone Tobie. Napisz program, który wyznaczy wartość największej możliwej minimalnej odległości między pewną parą przekaźników.

Wejście

W pierwszym wierszu wejścia dana jest jedna liczba naturalna N oznaczająca liczbę przekaźników. W następnych N wierszach dany jest opis możliwych współrzędnych każdego z przekaźników. i-ty opis składa się z dwóch liczb xi, yi oddzielonych pojedynczą spacją i oznaczające możliwe położenie i-tego przekaźnika.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczającą maksymalną minimalną odległość między pewną parą przekaźników.

Ograniczenia

2 ≤ N ≤ 10 000, 1 ≤ xi, yi ≤ 109.

W testach wartych 10% punktacji zachodzi dodatkowy warunek N ≤ 20.

W testach wartych 50% punktacji zachodzi dodatkowy warunek N ≤ 2 000.

Przykład

Wejście Wyjście Wyjaśnienie
3
1 3
2 5
1 9
4

Pierwszy przekaźnik można postawić w 1, drugi w 5 oraz trzeci w 9.