WU-两条直线 （C++代码）唯一题解！！！！

解题思路:

这题有一定的难度  
需要一定的时间来理解

参考代码:

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
using namespace std;  
  
const int N=100000;  
struct P{int x,y;};  
bool cmp(P a,P b){  
    if(a.x==b.x)return a.y<b.y;  
    return a.x<b.x;  
}  
P d[N+5];  
struct F{int max,min;};  
F fl[N+5],fr[N+5];  
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 check(double m,int n){  
    m*=2;  
    int i,j=0;  
    for(i=0;i<n;i++){  
        while(j<n&&d[j].x-d[i].x<=m)j++;  //找出最大的xj使xj-xi<=m,所以在xi到xj的这段区间的范围
是垂直线的范围之后找出[1,i-1]以及[j+1,n-1]范围内的最大的y和最小的y值，如果最大的y值减去最小的y值<=m，
则说明这是水平线的范围，则进行下一轮二分找出中点，找出更优解。
        double MAX=-1e10;  
        double MIN=1e10;  
        if(j!=n){  
            MAX=Max(MAX,fr[j].max);  
            MIN=Min(MIN,fr[j].min);  
        }  
        if(i-1>=0){  
            MAX=Max(MAX,fl[i-1].max);  
            MIN=Min(MIN,fl[i-1].min);  
        }  
     //   cout<<i<<" "<<j<<" "<<MAX<<" "<<MIN<<endl;  
        if(MAX-MIN<=m)return true;  
    }  
    return false;  
}  
void init(int n){  
    int i;  
    fl[0].min=fl[0].max=d[0].y;  
    for(i=1;i<n;i++){  
        fl[i].max=Max(fl[i-1].max,d[i].y); //fl[i]代表着前i个y坐标里面的最大值， 
        fl[i].min=Min(fl[i-1].min,d[i].y); //fl[i]代表着前i个y坐标里面的最小值。 
    }  
    fr[n-1].min=fr[n-1].max=d[n-1].y;  
    for(i=n-2;i>=0;i--){  
        fr[i].max=Max(fr[i+1].max,d[i].y); //fr[i]代表着后（n-i）个y坐标里面的最大值 
        fr[i].min=Min(fr[i+1].min,d[i].y);  //fr[i]代表着后（n-i)个y坐标里面的最小值 
    }  
}  
int main(){  
    int i,n;  
    cin>>n;  
    for(i=0;i<n;i++){  
        int x,y;  
        scanf("%d%d",&x,&y);  
        d[i].x=x+y;   
        d[i].y=x-y;  //将坐标轴按顺时针旋转45度。 
    }  
    sort(d,d+n,cmp);  //按x坐标从小到大的顺序排序 
    init(n);  
    double l=0.0;  
    double r=1000000000;  
    while(r-l>=0.01){  
        double m=(l+r)/2; //二分法判断答案
      //  cout<<m<<endl;  
        if(check(m,n))r=m;  
        else l=m;  
    }  
    printf("%.1f\n",r);  //分到不能再分之后 得出答案即为最小的最大的曼哈顿距离
    return 0;  
}