BZOJ 1038 半平面交

多么明显的半平面交。
答案一定在山的顶点处或者半平面交区域的顶点处。。
View Code
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <algorithm>
  6  
  7 #define N 555
  8 #define EPS 1e-7
  9 #define INF 1e12
 10  
 11 using namespace std;
 12  
 13 struct PO
 14 {
 15     double x,y;
 16     void prt() {printf("%lf     %lf\n",x,y);}
 17 }p[N],tp[N],s[N];
 18  
 19 int n,m;
 20  
 21 inline PO operator +(PO a,PO b)
 22 {
 23     a.x+=b.x; a.y+=b.y;
 24     return a;
 25 }
 26  
 27 inline PO operator -(PO a,PO b)
 28 {
 29     a.x-=b.x; a.y-=b.y;
 30     return a;
 31 }
 32  
 33 inline PO operator *(PO a,double k)
 34 {
 35     a.x*=k; a.y*=k;
 36     return a;
 37 }
 38  
 39 inline PO operator /(PO a,double k)
 40 {
 41     a.x/=k; a.y/=k;
 42     return a;
 43 }
 44  
 45 inline int dc(double x)
 46 {
 47     if(x>EPS) return 1;
 48     else if(x<-EPS) return -1;
 49     return 0;
 50 }
 51  
 52 inline double cross(const PO &a,const PO &b,const PO &c)
 53 {
 54     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
 55 }
 56  
 57 inline double dot(const PO &a,const PO &b,const PO &c)
 58 {
 59     return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
 60 }
 61  
 62 inline PO getpoint(const PO &a,const PO &b,const PO &c,const PO &d)
 63 {
 64     double k1=cross(a,d,c),k2=cross(b,c,d);
 65     return a+(b-a)*k1/(k1+k2);
 66 }
 67  
 68 inline bool onseg(const PO &a,const PO &b,const PO &c)
 69 {
 70     if(dc(dot(a,b,c))<=0) return true;
 71     return false;
 72 }
 73  
 74 inline void read()
 75 {
 76     scanf("%d",&n);
 77     for(int i=1;i<=n;i++) scanf("%lf",&p[i].x);
 78     for(int i=1;i<=n;i++) scanf("%lf",&p[i].y);
 79 }
 80  
 81 inline void getcut()
 82 {
 83     tp[1].x=tp[5].x=-INF; tp[1].y=tp[5].y=-INF;
 84     tp[2].x=INF,tp[2].y=-INF;
 85     tp[3].x=INF,tp[3].y=INF;
 86     tp[4].x=-INF,tp[4].y=INF;
 87     int cp=4,tc;
 88     for(int i=1;i<n;i++)
 89     {
 90         tc=0;
 91         for(int j=1;j<=cp;j++)
 92         {
 93             if(dc(cross(p[i],p[i+1],tp[j]))>=0) s[++tc]=tp[j];
 94             if(dc(cross(p[i],p[i+1],tp[j])*cross(p[i],p[i+1],tp[j+1]))<0)
 95                 s[++tc]=getpoint(p[i],p[i+1],tp[j],tp[j+1]);
 96         }
 97         s[tc+1]=s[1];
 98         for(int j=1;j<=tc+1;j++) tp[j]=s[j];
 99         cp=tc;
100     }
101     m=cp;
102 }
103  
104 inline void go()
105 {
106     getcut();
107     double ans=INF;
108     PO s1,t1,jd;
109     for(int i=1;i<=n;i++)
110     {
111         s1=p[i]; t1.x=s1.x,t1.y=520.1314;
112         for(int j=1;j<=m;j++)
113         {
114             jd=getpoint(s1,t1,s[j],s[j+1]);
115             if(onseg(jd,s[j],s[j+1])) ans=min(ans,jd.y-p[i].y);
116         }
117     }
118     for(int i=1;i<=m;i++)
119     {
120         s1=s[i]; t1.x=s[i].x; t1.y=520.1314;
121         for(int j=1;j<n;j++)
122         {
123             jd=getpoint(s1,t1,p[j],p[j+1]);
124             if(onseg(jd,p[j],p[j+1])) ans=min(ans,s[i].y-jd.y);
125         }
126     }
127     printf("%.3lf\n",ans);
128 }
129  
130 int main()
131 {
132     read(),go();
133     return 0;
134 }