http://acm.pku.edu.cn/JudgeOnline/problem?id=1181
Автобусные остановки
В городе Yong-In планируется создать сеть автобусных маршрутов с N автобусными остановками. Каждая остановка находится на некотором перекрестке. Поскольку Yong-In - современный город, на карте он представлен улицами с квадратными кварталами одинакового размера. Две из N остановок выбираются пересадочными станциями H1 и H2, которые будут соединены друг с другом прямым автобусным маршрутом, а каждая из оставшихся N - 2 остановок будет непосредственно соединена маршрутом с одной пересадочной станцией H2 или H2 (но не с обеими), и не соединена ни с одной из оставшихся остановок.
Расстояние между любыми двумя остановками определяется как длина кратчайшего пути по улицам города. Это означает, что если остановка представлена парой координат (x, y), то расстояние между двумя остановками (x1, y1) и (x2, y2) будет равно . Если остановки A и B соединены с одной и той же пересадочной станцией, например H1, то длина пути из A в B является суммой расстояний от A до H1 и от H1 до B. Если автобусные остановки A и B соединены с разными пересадочными станциями, например A с H1 и B с H2, то длина пути из A в B является суммой расстояний от A до H1, от H1 до H2 и от H2 до B.
Проектировщики города Yong-In хотят быть уверены, что любой житель города сможет добраться до любой точки города достаточно быстро. Поэтому проектировщики хотят сделать пересадочными станциями такие две остановки, чтобы в полученной сети автобусных маршрутов максимальная длина пути между любыми двумя остановками была минимальной.
Вариант P выбора пересадочных станций и соединения остановок с ними будет лучше варианта Q, если максимальная длина пути между любыми двумя остановками в варианте P будет меньше, чем в варианте Q. Ваша задача - написать программу вычисления максимальной длины пути между любыми двумя остановками для наилучшего варианта P выбора пересадочных станций и соединения остановок с ними.
ВВОД
Ваша программа должна читать стандартный ввод. Первая строка содержит положительное целое число N (2 <= N <= 500) - количество остановок. Каждая из оставшихся N строк содержит пару чисел x и y - координаты автобусной остановки. Координаты x и y - положительные целые числа <= 5000. Никакие две остановки не могут быть представлены одной и той же парой координат.
ВЫВОД
Ваша программа должна записать в стандартный вывод одну строку с единственным положительным числом - минимальной возможной длиной максимального пути между остановками.
ПРИМЕРЫ ВВОДА И ВЫВОДА
Пример 1:
ввод вывод
6 20
1 7
16 6
12 4
4 4
1 1
11 1
Пример 2:
ввод вывод
7 25
7 9
10 9
5 3
1 1
7 2
15 6
17 7
Рисунки ниже показывают сети автобусных маршрутов для приведенных примеров входных данных. Если в Примере 1 выбрать остановки 3 и 4 как пересадочные станции, то самый длинный путь будет или между остановками 2 и 5, или между остановками 2 и 1. Поскольку лучшего варианта выбрать пересадочные станции нет, ответом будет 20.
Для Примера 2, если в качестве пересадочных станций выбраны остановки 5 и 6, то самый длинный путь будет между остановками 2 и 7. Поскольку лучших вариантов нет, ответом будет 25.
