蜂窝网络

题目描述

有 n 个城市编号从 1 到 n 和 m 个信号发射塔编号从 1 到 m 都分布在一条直线上，如果选择直线上某个点的坐标为 0，则这 n 个城市的坐标可以描述为 a1​,a2​,…,an​，这 m 个信号发射塔的坐标可描述为 b1​,b2​,…,bm​。每个信号发射塔能为它左右不超过 r 的距离以内的城市提供上网流量，你的任务是确定 r 最小为多少时才能保证所有城市都有网络信号？Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

第一行包含两个正整数 n 和 m，分别表示城市的个数和信号发射塔的个数，第二行包含 n 个整数 a1​,a2​,…,an​，依次为每个城市的位置坐标，第三行包含 m 个整数 b1​,b2​,…,bm​，依次为每个信号发射塔的位置坐标。允许多个城市或信号发射塔位置相同。Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

仅有一个整数，能使所有城市都有网络信号覆盖的最小的 r 值。Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入输出样例

输入 #1Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3 2
-2 2 4
-3 0

输出 #1Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4

输入 #2Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

5 3
1 5 10 14 17
4 11 15

输出 #2Jdt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3

说明/提示

• 对于 30% 的数据，1≤n,m≤500，对于整数 i,j，∀i∈[1,n]，1≤ai​≤500，∀j∈[1,m]，1≤bj​≤500。
• 对于另外 70% 的数据，1≤n,m≤10^5，对于整数 i,j，∀i∈[1,n]，∀j∈[1,m]，−10^9≤ai​,bj​≤10^9。