问题 25070 --ADV-1 两条直线

25070: ADV-1 两条直线

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

给定平面上n个点。

求两条直线,这两条直线互相垂直,而且它们与x轴的夹角为45度,并且n个点中离这两条直线的曼哈顿距离的最大值最小。

两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和,一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。

数据规模与约定

对于30%的数据,n<=100。

对于另外30%的数据,坐标范的绝对值小于100。

对于100%的数据,n<=105

输入

第一行包含一个数n。

接下来n行,每行包含两个整数,表示n个点的坐标(横纵坐标的绝对值小于109)。

输出

输出一个值,表示最小的最大曼哈顿距离的值,保留一位小数。

样例输入

4
1 0
0 1
2 1
1 2 

样例输出

1.0 

来源

 

[提交][状态]