#1521. 「HCOI-R2」哀之距
「HCOI-R2」哀之距
题目描述
哀遇到的猫可看作一个平面,上面有 个矩形。
第 个矩形的左下角坐标为 ,右上角坐标为 。
求其中距离最大的两个矩形的距离。
两个矩形的距离定义为各在内部(包括四条边上)任取一点的切比雪夫距离的最小值。
切比雪夫距离: 和 的切比雪夫距离为 。
输入格式
第一行一个整数 ,表示矩形个数。
接下来 行,第 行四个整数 ,表示第 个矩形。
输出格式
一行一个整数,表示任意两个矩形的距离的最大值。
样例
5
1 2 5 2
4 0 4 4
3 3 7 3
0 5 3 5
2 1 2 6
3
题目来源:洛谷 P12351