Олимпиадный тренинг

Задача . C. Сотовая связь


Задача

Темы: Бинарный поиск два указателя реализация *1500

На прямой заданы n точек — позиции населенных пунктов, а также m точек — позиции вышек сотовой связи. Все вышки работают одинаково, они обеспечивают сотовой связью все населенные пункты, которые удалены от нее не более чем на r.

Перед вами стоит задача определить минимальное r, чтобы каждый населенный пункт был обеспечен сотовой связью. Иными словами надо найти наименьшее r такое, что для каждого города найдется хотя бы одна вышка на расстоянии не более чем r.

Если r = 0, то вышка обеспечивает сотовой связью только ту точку, где она расположена. Одна вышка может обеспечивать сотовой связью любое количество населенных пунктов, при условии, что все они расположены от неё на расстоянии не более чем r.

Входные данные

В первой строке следует два целых положительных числа n и m (1 ≤ n, m ≤ 105) — количество населенных пунктов и количество вышек.

Во второй строке следует последовательность из n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — координаты населенных пунктов. Допустимо, что в одной точке может быть несколько населенных пунктов. Все координаты населенных пунктов заданы в порядке неубывания.

В третьей строке следует последовательность из m целых чисел b1, b2, ..., bm ( - 109 ≤ bj ≤ 109) — координаты вышек сотовой связи. Допустимо, что в одной точке может быть несколько вышек. Все координаты вышек заданы в порядке неубывания.

Выходные данные

Выведите минимальное число r такое, что каждый населенный пункт будет обеспечен сотовой связью.


Примеры
№Входные данныеВыходные данные
1 3 2
-2 2 4
-3 0 
4
2 5 3
1 5 10 14 17
4 11 15 
3

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет