#1521. 「HCOI-R2」哀之距

「HCOI-R2」哀之距

题目描述

哀遇到的猫可看作一个平面,上面有 nn 个矩形。

第 ii 个矩形的左下角坐标为 (xi,0,yi,0)(x_{i,0},y_{i,0}),右上角坐标为 (xi,1,yi,1)(x_{i,1},y_{i,1})。

求其中距离最大的两个矩形的距离。

两个矩形的距离定义为各在内部(包括四条边上)任取一点的切比雪夫距离的最小值。

切比雪夫距离:(a,b)(a,b) 和 (c,d)(c,d) 的切比雪夫距离为 max⁡(∣a−c∣,∣b−d∣)\max(|a-c|,|b-d|)。

输入格式

第一行一个整数 nn,表示矩形个数。

接下来 nn 行,第 ii 行四个整数 xi,0,yi,0,xi,1,yi,1x_{i,0}, y_{i,0}, x_{i,1}, y_{i,1},表示第 ii 个矩形。

输出格式

一行一个整数,表示任意两个矩形的距离的最大值。

样例

5
1 2 5 2
4 0 4 4
3 3 7 3
0 5 3 5
2 1 2 6
3

题目来源:洛谷 P12351