求两条直线这两条直线互相垂直而且它们与x轴的夹角为45度并且n个点中离这两条直线的曼哈顿距离的最大值最小。
两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。
输入格式 第一行包含一个数n。
接下来n行每行包含两个整数表示n个点的坐标横纵坐标的绝对值小于10^9。
输出格式 输出一个值表示最小的最大曼哈顿距离的值保留一位小数。 样例输入 4 1 0 0 1 2 1 1 2 样例输出 1.0 数据规模与约定 对于30%的数据n<100。
对于另外30%的数据坐标范的绝对值小于100。
对于100%的数据n<105。
解题思路
这题挺难理解的刚上手不大有思路编者也是借鉴了https://blog.dotcpp.com/a/3702 首先明确题意点到直线的距离为点到两条直线距离中的较小者然后我们要找 所有点到直线的距离的最大值并且要这个最大值越小越好。编程语文理解也要好不知道读者有没有被我绕晕 其次要明确曼哈顿距离的概念曼哈顿距离又称街区距离因为两点间的不可直接到达只能通过垂直水平方向的道路到达称为街区距离很形象。如下图 
如果只有一条直线那么不难得出结论让直线卡在最远的两个点的正中间这样点到直线的最大距离最小如下图所示。但是本题中有两条直线点到哪个直线近距离就为哪一个这样要考虑的情况很多两条直线分下移上移讨论编者认为要分成四个象限讨论。 
如果只有一条直线那么上图直线的位置为最优距离为ab两点距离的一半。
这时候我们要一个一个试出答案也就是枚举因为精度要求为0.1如果以步长为0.1枚举最差要试10^ 10次肯定是不可取的较好的做法是采用二分法的办法第一次取总区间长度的一半如果满足条件那么就要减少距离就是在左区间继续枚举如果不满足就把距离加大也就是在右区间枚举直到 右区间端点-左区间端点的值小于0.1达到了精度要求 。 那么如何判断一次枚举满不满足要求呢难道要把n个点的两个距离求出来么这样肯定是不行的。那么注意这两条直线是垂直的而且与坐标轴夹角为45^ 这样我们可以把原来的坐标轴逆时针旋转45^ 这样点到两条直线的距离就可以转换为xy坐标原来的(0,1) 为新坐标系的(1,1) 如下图 
转换公式为d[i].xxy; d[i].yy-x;
这样点到直线的距离就变成了点的x y坐标的绝对值变换坐标系以后还得继续提高算法的效率 假设当前最小距离为m先对横坐标x排序新的坐标系然后我们忽略x坐标在2* m内的点因为不论y的距离为多少题目要求是两者的小的所以已经满足了要求注意是2* m还记得只考虑一条直线时我们得出的结论么把直线卡在两个最远的点的中间那么最大距离就为m了。那么就只要考虑在区间2* m两端外面的点此时再考虑y距离若y两端的距离的差值小于2* m同样的我们把另一条直线插在这两点中间那么也可以使他们的y坐标满足要求这里两条直线是可以随意移动的互不干扰你可以想象为x y两个坐标轴的移动如果x方向最远的两点相距2 * m那么就把y轴放到两点的正中间这样两点到y轴的水平距离就都为m了y方向同理。
代码如下有详细地注释
#include #include #include #include using namespace std; const int N100000; struct P{int x,y;}; //构造一个点地结构体P d[N5]; struct F{int max,min;}; //用来存储y方向的最大最小值F fl[N5],fr[N5]; inline double Max(double a,double b){return a>b?a:b;} //返回最大值inline double Min(double a,double b){return a>b?b:a;} //返回最小值bool cmp(P a,P b){ //用于sort函数按x的升序和y的升序排列if(a.xb.x)return a.y