#Pold1020. 算法提高 两条直线

    ID: 356 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>蓝桥杯-算法提高赛制:ACM来源:蓝桥杯练习系统 ID: 19 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T19二分答案离散化

算法提高 两条直线

算法提高 两条直线

题目描述

给定平面上n个点。

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

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

输入格式

输入描述:

第一行包含一个数n。

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

输入样例: 4 1 0 0 1 2 1 1 2

输出格式

输出描述: 输出一个值,表示最小的最大曼哈顿距离的值,保留一位小数。 输出样例: 1.0

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:1.0s 内存限制:256.0MB

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

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

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