BZOJ1038 瞭望塔

学习了半平交面。

我这里写的是训练指南中的双端队列，每次判断是否删去更优然后更新。

看hzwer中有一处不太明白就是为何要将两段加入队列

后来对拍出错才知道是因为精度，当两线重合时他们叉积返回值是一个极小值

所以判断一下精度即可。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;

 int n,m,cnt,tot;double ans=1e20,eps=1e-;

 struct point{

     double x,y;

 }a[N],p[N];

 point operator -(point a,point b){

     point t;t.x=b.x-a.x;t.y=b.y-a.y;

     return t;

 }

 double operator *(point a,point b){

     return a.x*b.y-a.y*b.x;

 }

 struct line{

     point a,b;double slop;

     bool operator <(const line &B)const{

         return slop==B.slop?(b-a)*(B.b-a)>:slop<B.slop;

     }

 }l[N],s[N];

 point inter(line a,line b){

     double k1,k2,t;

     k1=(b.b-a.a)*(a.b-a.a);

     k2=(a.b-a.a)*(b.a-a.a);

     t=k1/(k1+k2);

     point ans;

     ans.x=b.b.x+(b.a.x-b.b.x)*t;

     ans.y=b.b.y+(b.a.y-b.b.y)*t;

     return ans;

 }

 bool jud(line a,line b,line t)

 {

     point pp=inter(a,b);

     return (t.b-t.a)*(pp-t.a)<-eps;

 }

 void hpl()

 {

     int L=,R=;

     for(int i=;i<=cnt;++i)

     {

         if(l[i].slop!=l[i-].slop)++tot;

         l[tot]=l[i];

     }

     cnt=tot;tot=;

     s[++R]=l[];s[++R]=l[];

     for(int i=;i<=cnt;++i)

     {

         while(L<R&&jud(s[R-],s[R],l[i]))R--;

         while(L<R&&jud(s[L+],s[L],l[i]))L++;

         s[++R]=l[i];

     }

     while(L<R&&jud(s[R-],s[R],s[L]))R--;

     while(L<R&&jud(s[L+],s[L],s[R]))L++;

     for(int i=L;i<R;++i)

     a[++tot]=inter(s[i],s[i+]);

 }

 void getans()

 {

     for(int i=;i<=tot;++i)

     {

         point t;t.x=a[i].x;t.y=-;

         for(int j=;j<n;++j)

         if(p[j].x<=a[i].x&&p[j+].x>=a[i].x)

         ans=min(ans,a[i].y-inter((line){p[j],p[j+]},(line){t,a[i]}).y);

     }

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

     {

         point t;t.x=p[i].x;t.y=-;

         for(int j=;j<tot;++j)

         if(a[j].x<=p[i].x&&a[j+].x>=p[i].x)

         ans=min(ans,inter((line){a[j],a[j+]},(line){t,p[i]}).y-p[i].y);

     }

 }

 int main()

 {

 //    freopen("1.out","r",stdin);

 //    freopen("my.out","w",stdout);

     scanf("%d",&n);

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

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

 //    p[0].x=p[1].x;p[0].y=1e9;

 //    p[n+1].x=p[n].x;p[n+1].y=1e9;

     for(int i=;i<n;++i)l[++cnt].a=p[i],l[cnt].b=p[i+];

     if(cnt<){

         puts("0.000");return ;

     }

     for(int i=;i<=cnt;++i)

     l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);

     sort(l+,l++cnt);

     hpl();

     getans();

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

     return ;

 }