【CodeForces】702C - Cellular Network（二分）

点击打开题目

C. Cellular Network

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.

Input

The first line contains two positive integers n and m (1 ≤ n, m ≤ 105) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.

The third line contains a sequence of m integers b1, b2, ..., bm ( - 109 ≤ bj ≤ 109) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.

Output

Print minimal r so that each city will be covered by cellular network.

Examples

input

3 2
-2 2 4
-3 0

output

4

input

5 3
1 5 10 14 17
4 11 15

output

3

上道题刚说碰上这种的就二分，这道题就来了。

刚开始直接写了个对半径二分的方法，没跑几组就TLE了，果然跟估计的复杂度差不多。

那么就想到了个新方法：算出距每个城市最近的塔的距离，然后取这个距离的最大值就行啦。找距离的时候用二分去查找，这个范围就小很多了。

另外有一点，找到一个塔的坐标pos大于该城市，应该再看看塔的坐标小于该城市的那个塔距离是多少，而坐标小于那个城市的塔的坐标是pos - 1。然后就又出现了一个新问题，如果找到的是最后一个塔或者是第一个塔的时候呢？我们这样赋值一下：b [ 0 ] = b [ 1 ] b [ k + 1 ] = b [ k ]

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x7fffffff
#define MAX 100000
int a[MAX+11];
int b[MAX+11];
int main()
{
	int n,k;
	while (~scanf ("%d %d",&n,&k))
	{
		for (int i = 1 ; i <= n ; i++)
			scanf ("%d",&a[i]);
		for (int i = 1 ; i <= k ; i++)
			scanf ("%d",&b[i]);
		b[0] = b[1];		//变成INF也会出问题，还是这样赋值最好 
		b[k+1] = b[k];
		int ans = 0;
		int pos;
		int dis;		//城市与塔的最近距离 
		for (int i = 1 ; i <= n ; i++)
		{
			pos = lower_bound (b+1 , b+1+k , a[i]) - b;
			dis = min (abs(a[i]-b[pos]) , abs(a[i] - b[pos-1]));
			ans = max (ans , dis);
		}
		printf ("%d\n",ans);
	}
	return 0;
}