Autobusy
Limit pamięci: 32 MB
Prezydent Bajtogrodu planuje budowę sieci komunikacyjnej,
składającej się z przystanków i linii autobusowych. Dwa spośród
przystanków, i zostaną wybrane na węzły przesiadkowe, a
pozostałe przystanków zostanie połączonych bezpośrednimi
liniami autobusowymi z albo (ale nie z obydwoma jednocześnie). Ponadto, w mieście zostanie utworzona linia
autobusowa łącząca obydwa węzły przesiadkowe. Z powodu braku funduszy, nie powstaną żadne inne
połączenia autobusowe.
Odległość pomiędzy przystankami autobusowymi połączonymi bezpośrednią
linią autobusową, znajdującymi się w punktach o współrzędnych i wynosi . Jeżli dwa
przystanki połączone są bezpośrednio z tym samym węzłem, to odległość
między nimi jest sumą odległości obydwóch przystanków od tego węzła.
Jeśli dwa przystanki połączone są z różnymi węzłami przesiadkowymi, to
odległość między nimi jest sumą odległości każdego z przystanków od
węzła do którego jest on podłączony i odległości pomiędzy węzłami przesiadkowymi.
Zadanie
Napisz program, który:
- wczyta rozmieszczenie przystanków autobusowych ze standardowego wejścia,
- wyznaczy przystanki, które należy wybrać jako węzły przesiadkowe oraz pary przystanków, które należy połączyć bezpośrednimi liniami autobusowymi, tak aby maksymalna odległość pomiędzy dowolnymi dwoma przystankami była jak najmniejsza,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszej lini standardowego wejścia znajudje się jedna liczba całkowita (), oznaczająca liczbę wszystkich przystanków w mieście. Każda z kolejnych linii zawiera dwie liczby całkowite dodatnie, nie większe niż - są to współrzędne jednego z przystanków autobusowych. W danym punkcie może znajdować się co najwyżej jeden przystanek.
Wyjście
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia wypisać jedną liczbę całkowitą - największą odległość pomiędzy dwoma przystankami autobusowymi w mieście, przy optymalnym doborze węzłów przesiadkowych i połączeniu przystanków z węzłami.
Przykład
Dla danych wejściowych:
6
1 7
16 6
12 4
4 4
1 1
11 1
poprawną odpowiedzią jest:
20
Przykładowym danym wejściowym odpowiada powyższy schemat. Przystanki numer 3 i 4 zostały wybrane na węzły przesiadkowe.
Zapożyczone ze starego IOI przez Jakuba Łąckiego.