#4141
两条直线
两条直线
题目描述
给定平面上n个点。 求两条直线,这两条直线互相垂直,而且它们与x轴的夹角为45度,并且n个点中离这两条直线的曼哈顿距离的最大值最小。 两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和,一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。输入格式
第一行包含一个数n。 接下来n行,每行包含两个整数,表示n个点的坐标(横纵坐标的绝对值小于109)。输出格式
输出一个值,表示最小的最大曼哈顿距离的值,保留一位小数。样例
42
6334 18467
19169 26500
11478 15724
26962 29358
5705 24464
23281 28145
9961 16827
2995 491
4827 11942
32391 5436
3902 14604
292 153
17421 12382
19718 18716
5447 19895
14771 21726
1869 11538
25667 19912
17035 26299
28703 9894
31322 23811
17673 30333
15141 4664
28253 7711
25547 6868
32662 27644
20037 32757
8723 12859
27529 9741
12316 778
22190 3035
288 1842
9040 30106
19264 8942
27446 22648
15890 23805
24370 6729
15006 15350
24393 31101
19629 3548
24084 12623
18756 19954
12129.0
说明/提示
与约定 对于30%的数据,n<=100。 对于另外30%的数据,坐标范的绝对值小于100。 对于100%的数据,n<=105。