洛谷 P1663 山 题解

分享一种时间复杂度 $O\left(N\log N\right)$（不是其他题解的 $O\left(N\log ans\right)$）的做法，理论上可以跑过 $N=5\times 10^6$ 甚至更大的数据。

首先我们观察这张图。

发现对于蓝色线段，只有红色直线上侧的点能看到这条线段。

而我们想要所有的线段都被看到，于是对所有线段所对应的直线上侧求 半平面交，答案就是所得图形的最低点。

在本题中求半平面交时维护的一定是一个下凸壳，那么答案必然是下凸壳其中一个顶点的 $y$ 坐标。

时间复杂度分析：半平面交核心代码 $O\left(N\right)$，排序 $O\left(N\log N\right)$，总复杂度 $O\left(N\log N\right)$。

注意一个小细节，题目中说灯必须要装在山上，于是加两个半平面 $x\ge X_1$ 和 $x\le X_N$ 作为限制。

代码如下。

#include<bits/stdc++.h>
const double eps=1e-9;
using namespace std;
struct vec{
    double x,y;
    vec(const double&x_=0,const double&y_=0){x=x_,y=y_;}
    vec operator+(const vec&b)const{return vec(x+b.x,y+b.y);}
    vec operator-(const vec&b)const{return vec(x-b.x,y-b.y);}
    double operator*(const vec&b)const{return  x*b.x+y*b.y ;}
    double times    (const vec&b)const{return  x*b.y-y*b.x ;}
    void print()const{cout<<'('<<x<<','<<y<<')'<<endl;}
    double deg()const{return::atan2(x,y);}
};
struct segment{
    vec OA,OB;
    vec AB()const{return OB-OA;}
    segment(vec OA_=vec(),vec OB_=vec()){OA=OA_,OB=OB_;}
    bool is_cw(const vec&b)const{return AB().times(b-OA)<-eps;}
    vec inter(const segment&b)const{
        double a_1,b_1,c_1;
        if(fabs(  AB().x)<eps) a_1=1,b_1=0,c_1=  OA.x;
        else{
            a_1=  OA.y       /(  OA.x-  OB.x)+
                  OB.y       /(  OB.x-  OA.x);
            c_1=  OA.y*  OB.x/(  OA.x-  OB.x)+
                  OB.y*  OA.x/(  OB.x-  OA.x);
            b_1=-1;
        }
        double a_2,b_2,c_2;
        if(fabs(b.AB().x)<eps) a_2=1,b_2=0,c_2=b.OA.x;
        else{
            a_2=b.OA.y       /(b.OA.x-b.OB.x)+
                b.OB.y       /(b.OB.x-b.OA.x);
            c_2=b.OA.y*b.OB.x/(b.OA.x-b.OB.x)+
                b.OB.y*b.OA.x/(b.OB.x-b.OA.x);
            b_2=-1;
        }
        double d=vec(a_1,b_1).times(vec(a_2,b_2));
        return vec(
            vec(c_1,b_1).times(vec(c_2,b_2))/d,
            vec(a_1,c_1).times(vec(a_2,c_2))/d
        );
    }
    bool operator<(const segment&b)const{
        return AB().deg()<b.AB().deg();
    }
};
constexpr int maxn=5005;
int N,M,K;vec A[maxn];double Ans=INFINITY;
segment P[maxn],Seg[maxn];deque<segment>Q;
vec  back_point(){return(----Q.end())->inter(*--Q.end());}
vec front_point(){return(++Q.begin())->inter(*Q.begin());}
int read(){
    int f=1,ret=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f; ch=getchar();}
    while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return f*ret;
}
int main(){
    N=read()+2;
    for(int i=2;i< N;i++) scanf("%lf%lf",&A[i].x,&A[i].y);
    A[1].x=A[2].x,A[1].y=A[2].y+1,A[N].x=A[N-1].x,A[N].y=A[N-1].y+1;
    for(int i=1;i< N;i++) P[++K]=segment(A[i],A[i+1]);
    sort(P+1,P+K+1);
    reverse(P+1,P+K+1);
    for(int i=1;i<=K;i++){
        while(Q.size()>1&&P[i].is_cw( back_point())) Q.pop_back ();
        while(Q.size()>1&&P[i].is_cw(front_point())) Q.pop_front();
        while(Q.size()&&fabs(P[i].AB().deg()-Q.back().AB().deg())<eps
              &&P[i].is_cw(Q.back().OA)) Q.pop_back();
        if(Q.empty()||fabs(Q.back().AB().deg()-P[i].AB().deg())>eps)
            Q.push_back(P[i]);
        if(Q.size()>1&&Q.front().is_cw(back_point())) Q.pop_back();
    }
    if(Q.size()>=2){
        K=0;for(auto&x:Q) Seg[++K]=x;
        for(int i=1;i< K;i++) if(abs(Seg[i].AB().deg()-Seg[i+1].AB().deg())>eps)
            Ans=min(Ans,Seg[i].inter(Seg[i+1]).y);
    }
    printf("%.2lf\n",Ans);
    return 0;
}