扩散

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 ppg.in 输出文件 ppg.out

【问题描述】
在平面上有n个点，一个点每过一个单位时间就会向4个方向（上下左右）扩散一个距离，如下图所示：

两个点a和b连通，记作e(a,b)，当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),……e(ak,v)。给定平面上n个点的坐标，问最早什么时刻它们形成一个连通块。
【输入文件】
第一行一个数：n
下面n行，每行两个整数x,y，代表一个点的坐标。
【输出文件】
一个整数，表示最早的时刻所有点形成的连通块。
【样例输入】
2
0 0
5 5
【样例输出】
5
【数据规模】
对于20%的数据，满足1<=n<=5; 1<=x[i],y[i]<=50;
对于100%的数据，满足1<=n<=50;1<=x[i],y[i]<=10^9