0338. Лес

Путь в школу у Васи лежит через лес. В зимнее время идти этой извилистой дорогой особенно тяжело, поскольку снег никто не расчищает и приходится затрачивать уйму усилий, чтобы сделать очередной шаг. Из-за этого Вася постоянно жалуется своему отцу, высокопоставленному чиновнику. Однажды терпение отца лопнуло, и он решил расчистить дорогу к школе. Для уменьшения времени на расчистку было принято решение, что дорога к школе должна быть сплошной полосой, проходящей через весь лес насквозь.

Вам предложена карта (вид на лес сверху), на которой изображены все деревья. Зная координаты деревьев, требуется построить максимально широкую горизонтальную полосу ненулевой ширины с границами, параллельными оси OX, проходящую через лес таким образом, чтобы и сверху, и снизу от неё находилось хотя бы одно дерево. При этом вычищенная дорога не должна содержать внутри себя деревьев, но может касаться их своей границей.

Требуется написать программу, определяющую ширину максимальной допустимой дороги, которую можно проложить через лес.

Формат входного файла

В первой строке файла содержится натуральное число n – число деревьев в лесу (1 ≤ n ≤ 100000). В следующих n строках содержатся координаты деревьев – целые числа x_i, y_i (0 ≤ x_i, y_i ≤ 10⁸).

Формат выходного файла

Выведите максимальную ширину полосы, либо -1, если вам не удалось определить дорогу, удовлетворяющую описанным выше требованиям.

Пример:

Примечание:

Решения, работающие при n ≤ 10000 будут оцениваться из 70 баллов.

Источник: VII сетевая районная олимпиада Республики Карелия по информатике, XXIV Городская олимпиада школьников по информатике

Обсудить       Отправить решение



Версия для печати