Luogu-2600 [ZJOI2008]瞭望塔

时间：2023-03-10 02:43:08
Luogu-2600 [ZJOI2008]瞭望塔

把地面看成半平面，能看到所有位置的点所在的区域即为半平面的交

因为分段函数的极值只会在转折处或边界取到，所以对于半平面上和地面上的每一个交点都求一下距离就好了

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e3+100;

const double maxx=4e12;

struct Point{

    double x,y;

    Point(double xx=0,double yy=0){

        x=xx,y=yy;

    }

}a[maxn],p[maxn];

struct Vector{

    double x,y;

    Vector(double xx=0,double yy=0){

        x=xx,y=yy;

    }

};

struct Line{

    Point p;

    Vector v;

    double ang;

    Line(Point a=Point(),Vector b=Vector()){

        p=a,v=b;

        ang=atan2(v.y,v.x);

    }

}q[maxn],b[maxn];

int dcmp(double x){return fabs(x)<1e-10?0:(x>0?1:-1);}

Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}

Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}

Vector operator * (double p,Vector a){return Vector(a.x*p,a.y*p);}

double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}

double operator * (Point a,Point b){return a.x*b.y-a.y*b.x;}

bool operator < (Point a,Point b){return dcmp(a.x-b.x)==0?(dcmp(a.y-b.y)<0):(a.x<b.x);}

bool operator < (Line a,Line b){return dcmp(a.ang-b.ang)==0?(dcmp(a.v*(b.p-a.p))>0):(a.ang<b.ang);}

double len(Vector a){return sqrt(a.x*a.x+a.y*a.y);}

Point glt(Line a,Line b){Vector v=a.p-b.p; return a.p+b.v*v/(a.v*b.v)*a.v;}

bool onright(Line a,Line b,Line t){Point p=glt(a,b); return dcmp(t.v*(p-t.p))<0;}

void bpm(Line *b,int &n,Point *p){

    sort(b+1,b+n+1);

    int l=0,r=1,tot=0;

    for(int i=1;i<=n;i++){

        if(b[i].ang!=b[i-1].ang) tot++;

        b[tot]=b[i];

    }

    n=tot,q[0]=b[1],q[1]=b[2];

    for(int i=3;i<=n;i++){

        while(l<r&&onright(q[r],q[r-1],b[i])) r--;

        while(l<r&&onright(q[l],q[l+1],b[i])) l++;

        q[++r]=b[i];

    }

    while(l<r&&onright(q[r],q[r-1],q[l])) r--;

    while(l<r&&onright(q[l],q[l+1],q[r])) l++;

    n=0,q[r+1]=q[l];

    for(int i=l;i<=r;i++)

        b[++n]=q[i],p[n]=glt(q[i],q[i+1]);

}

int n;

void solve(Point *a,int m,Point *p,int n){

    sort(p+1,p+n+1);

//	for(int i=1;i<=n;i++) printf("%lf %lf\n",p[i].x,p[i].y);

    int l=2;

    double ans=maxx*2;

    for(int i=1;i<n;i++){

        while(l<m&&dcmp(p[i].x-a[l+1].x)>0) l++;

        Point pz=glt(Line(a[l],a[l+1]-a[l]),Line(p[i],Vector(0,1)));

        ans=min(ans,len(pz-p[i]));

    }

    l=1;

    for(int i=2;i<m;i++){

        while(l<n&&dcmp(a[i].x-p[l+1].x)>0) l++;

        Point pz=glt(Line(p[l],p[l+1]-p[l]),Line(a[i],Vector(0,1)));

        ans=min(ans,len(pz-a[i]));

    }

    printf("%.3lf\n",ans);

}

int main(){

    scanf("%d",&n),n++;

    for(int i=2;i<=n;i++) scanf("%lf",&a[i].x);

    for(int i=2;i<=n;i++) scanf("%lf",&a[i].y);

    a[1]=Point(a[2].x,maxx),a[n+1]=Point(a[n].x,maxx);

    int m=n+1;

    for(int i=1;i<=n;i++)

        b[i]=Line(a[i],a[i+1]-a[i]);

    bpm(b,n,p);

    solve(a,m,p,n);

    return 0;

}

相关文章