BZOJ 1007 [HNOI2008]水平可见直线

题解：
维护一个栈就好了，画画图就知道怎么维护了。。
这两天总写不对计算几何的水题。。真是郁闷。。
View Code
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <algorithm>
  6 
  7 #define N 555555
  8 #define EPS 1e-7
  9 
 10 using namespace std;
 11 
 12 struct PO
 13 {
 14     double x,y;
 15     void prt() {printf("%lf       %lf\n",x,y);}
 16 }sk[N];
 17 
 18 struct LI
 19 {
 20     PO a,b;
 21     int id;
 22     double p,q;
 23     void prt() {printf("%lf     %lf     %lf     %lf\n",a.x,a.y,b.x,b.y);}
 24 }li[N],stk[N];
 25 
 26 int n,top,tp,bh[N];
 27 
 28 inline PO operator +(PO a,PO b)
 29 {
 30     a.x+=b.x; a.y+=b.y;
 31     return a;
 32 }
 33 
 34 inline PO operator -(PO a,PO b)
 35 {
 36     a.x-=b.x; a.y-=b.y;
 37     return a;
 38 }
 39 
 40 inline PO operator *(PO a,double k)
 41 {
 42     a.x*=k; a.y*=k;
 43     return a;
 44 }
 45 
 46 inline PO operator /(PO a,double k)
 47 {
 48     a.x/=k; a.y/=k;
 49     return a;
 50 }
 51 
 52 inline int dc(double x)
 53 {
 54     if(x>EPS) return 1;
 55     else if(x<-EPS) return -1;
 56     return 0;
 57 }
 58 
 59 inline void read()
 60 {
 61     scanf("%d",&n);
 62     double a,b;
 63     for(int i=1;i<=n;i++)
 64     {
 65         scanf("%lf%lf",&a,&b);
 66         li[i].a.x=0; li[i].a.y=b;
 67         if(dc(a)==0) li[i].b.x=29.3278,li[i].b.y=b;
 68         else li[i].b.x=29.3278,li[i].b.y=a*29.3278+b;
 69         li[i].p=a; li[i].q=b;
 70         li[i].id=i;
 71     }
 72 }
 73 
 74 inline double cross(const PO &a,const PO &b,const PO &c)
 75 {
 76     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
 77 }
 78 
 79 inline bool cmp(const LI &a,const LI &b)
 80 {
 81     if(dc(a.p-b.p)==0) return a.q>b.q;
 82     return a.p<b.p;
 83 }
 84 
 85 inline PO getpoint(const PO &a,const PO &b,const PO &c,const PO &d)
 86 {
 87     double k1=cross(a,d,c),k2=cross(b,c,d);
 88     PO tmp;tmp=b-a;
 89     return a+tmp*k1/(k1+k2);
 90 }
 91 
 92 inline void go()
 93 {
 94     PO c;
 95     sort(li+1,li+1+n,cmp);
 96     top=tp=0;
 97     for(int i=1;i<=n;i++)
 98     {
 99         if(dc(li[i].p-li[i-1].p)==0) continue;
100         while(tp>=1)
101         {
102             c=getpoint(li[i].a,li[i].b,stk[top].a,stk[top].b);
103             if(dc(c.x-sk[tp].x)<=0) top--,tp--;
104             else break;
105         }
106         stk[++top]=li[i];
107         if(top==2&&tp==0) sk[++tp]=getpoint(stk[top].a,stk[top].b,stk[top-1].a,stk[top-1].b);
108         else if(tp>0) sk[++tp]=c;
109     }
110     for(int i=1;i<=top;i++) bh[i]=stk[i].id;
111     sort(bh+1,bh+1+top);
112     for(int i=1;i<top;i++) printf("%d ",bh[i]);
113     printf("%d",bh[top]);
114 }
115 
116 int main()
117 {
118     read(),go();
119     return 0;
120 }