bzoj1038(半平面交)

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

const double eps=1e-;

double ans=1e10;

int n,head,tail;

struct vec{

    double x,y;

    vec(double x=,double y=):x(x),y(y){}

    vec operator-(vec& a){

        return vec(x-a.x,y-a.y);

    }

    vec operator+(vec&a){

        return vec(x+a.x,y+a.y);

    }

}po[maxn],g[maxn];

vec operator*(vec a,double t){return vec(a.x*t,a.y*t);}

double cross(vec a,vec b){return a.x*b.y-b.x*a.y;}

struct lin{

    vec p,v;//p是直线上一个点，v是方向向量

    double ang;//ang是斜率;

    lin(){}

    lin(vec p,vec v):p(p),v(v){ang=atan2(v.y,v.x);}

    bool operator<(const lin&a)const{

        return ang<a.ang;

    }

}ll[maxn],q[maxn],bb,cc;

bool onl(lin L,vec p){

    return cross(L.v,p-L.p)>;

}

vec qj(lin a,lin b){

    vec u=a.p-b.p;

    double t=cross(b.v,u)/cross(a.v,b.v);

    return a.v*t+a.p;

}

void halfj(){

    sort(ll,ll+n);

    q[head=tail=]=ll[];

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

        while(head<tail&&!onl(ll[i],g[tail-]))tail--;

        while(head<tail&&!onl(ll[i],g[head]))head++;

        q[++tail]=ll[i];

        if(fabs(cross(q[tail].v,q[tail-].v))<eps){

            --tail;if(onl(q[tail],ll[i].p))q[tail]=ll[i];

        }

        if(head<tail)g[tail-]=qj(q[tail-],q[tail]);

    }

    while(head<tail&&!onl(q[head],g[tail-]))--tail;

}

int main(){

    cin>>n;

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

        scanf("%lf",&po[i].x);

    }

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

        scanf("%lf",&po[i].y);

    }

    po[].x=po[].x;po[].y=;

    po[n+].x=po[n].x;po[n+].y=;

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

        ll[i]=lin(po[i],po[i+]-po[i]);

    }

    n+=;

    halfj();

    for(int k=;k<tail;++k)

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

            vec tmp;tmp.x=g[k].x;tmp.y=-;

            if(g[k].x>=po[i].x&&g[k].x<=po[i+].x){

                cc=lin(po[i],po[i+]-po[i]);

                bb=lin(tmp,g[k]-tmp);

                ans=min(ans,g[k].y-qj(cc,bb).y);

            }

    }

    for(int k=;k<=n-;++k)

        for(int i=;i<tail-;++i){

            vec tmp;tmp.x=po[k].x;tmp.y=-;

            if(po[k].x>=g[i].x&&po[k].x<=g[i+].x){

                cc=lin(g[i],g[i+]-g[i]);

                bb=lin(tmp,po[k]-tmp);

                ans=min(ans,qj(cc,bb).y-po[k].y);

            }

    }

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

    return ;

}