Problem 1659 --两条直线1659: 两条直线
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$4$ |
正确数量 |
$2$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
几何 |
当前分类(单击移除)：
几何
单击选择分类：
算法提高 两条直线
时间限制：1.0s 内存限制：256.0MB
问题描述
给定平面上n个点。
求两条直线，这两条直线互相垂直，而且它们与x轴的夹角为45度，并且n个点中离这两条直线的曼哈顿距离的最大值最小。
两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和，一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。
输入格式
第一行包含一个数n。
接下来n行，每行包含两个整数，表示n个点的坐标（横纵坐标的绝对值小于109）。
输出格式
输出一个值，表示最小的最大曼哈顿距离的值，保留一位小数。
样例输入
4
1 0
0 1
2 1
1 2
样例输出
1.0
数据规模与约定
对于30%的数据，n< =100。
对于另外30%的数据，坐标范的绝对值小于100。
对于100%的数据，n< =105。
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$12 $ms]
|
sqrjy
|
605736
|
2020-07-05 16:26:55 |
| 内存最少[$4372 $KB]
|
sqrjy
|
605736 |
2020-07-05 16:26:55 |
| 第一AC |
sqrjy |
605736
|
2020-07-05 16:26:55 |
| 第一挑战 |
淡意的温柔
|
582567 |
2020-05-11 15:50:07 |