POJ 2451 半平面交nlogn

题意：
半平面交面积
题解：
果断上模板了。
尼玛。。。我输出-0.0给wa了半天，，，抑郁。。。
这个好像没什么用。。。
View Code
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 #define N 222222
  9 #define EPS 1e-10
 10 #define SIDE 10000
 11 
 12 using namespace std;
 13 
 14 struct PO
 15 {
 16     double x,y;
 17     void prt()
 18     {
 19         printf("%lf       %lf\n",x,y);
 20     }
 21 }p[N],o;
 22 
 23 struct LI
 24 {
 25     PO a,b;
 26     double angle;
 27     void in(double x1,double y1,double x2,double y2)
 28     {
 29         a.x=x1; a.y=y1; b.x=x2; b.y=y2;
 30     }
 31     void prt()
 32     {
 33         printf("%lf     %lf      %lf    %lf\n",a.x,a.y,b.x,b.y);
 34     }
 35 }li[N],deq[N];
 36 
 37 int n,m,cnt;
 38 
 39 inline int dc(double x)
 40 {
 41     if(x>EPS) return 1;
 42     else if(x<-EPS) return -1;
 43     return 0;
 44 }
 45 
 46 inline PO operator -(PO a,PO b)
 47 {
 48     PO c;
 49     c.x=a.x-b.x; c.y=a.y-b.y;
 50     return c;
 51 }
 52 
 53 inline double cross(PO a,PO b,PO c)
 54 {
 55     return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
 56 }
 57 
 58 inline bool cmp(const LI &a,const LI &b)//极角排序，内侧在前 
 59 {
 60     if(dc(a.angle-b.angle)==0) return dc(cross(a.a,a.b,b.a))<0;
 61     return a.angle>b.angle;
 62 }
 63 
 64 inline PO getpoint(LI &a,LI &b)
 65 {
 66     double k1=cross(a.a,b.b,b.a);
 67     double k2=cross(a.b,b.a,b.b);
 68     PO tmp=a.b-a.a,ans;
 69     ans.x=a.a.x+tmp.x*k1/(k1+k2);
 70     ans.y=a.a.y+tmp.y*k1/(k1+k2);
 71     return ans;
 72 }
 73 
 74 inline void read()
 75 {
 76     for(int i=1;i<=n;i++)
 77     {
 78         scanf("%lf%lf%lf%lf",&li[i].a.x,&li[i].a.y,&li[i].b.x,&li[i].b.y);
 79         li[i].angle=atan2(li[i].b.y-li[i].a.y,li[i].b.x-li[i].a.x);
 80     }
 81     li[n+1].in(0,0,SIDE,0);
 82     li[n+2].in(0,SIDE,0,0);
 83     li[n+3].in(SIDE,0,SIDE,SIDE);
 84     li[n+4].in(SIDE,SIDE,0,SIDE);
 85     for(int i=n+1;i<=n+4;i++) li[i].angle=atan2(li[i].b.y-li[i].a.y,li[i].b.x-li[i].a.x);
 86     n+=4;
 87 }
 88 
 89 inline void getcut()
 90 {
 91     sort(li+1,li+1+n,cmp);
 92     m=1;
 93     for(int i=2;i<=n;i++)
 94         if(dc(li[i].angle-li[m].angle)!=0)
 95             li[++m]=li[i];
 96     deq[1]=li[1]; deq[2]=li[2];
 97     int bot=1,top=2;
 98     for(int i=3;i<=m;i++)
 99     {
100         while(bot<top&&dc(cross(li[i].a,li[i].b,getpoint(deq[top],deq[top-1])))<0) top--;
101         while(bot<top&&dc(cross(li[i].a,li[i].b,getpoint(deq[bot],deq[bot+1])))<0) bot++;
102         deq[++top]=li[i];
103     }
104     while(bot<top&&dc(cross(deq[bot].a,deq[bot].b,getpoint(deq[top],deq[top-1])))<0) top--;
105     while(bot<top&&dc(cross(deq[top].a,deq[top].b,getpoint(deq[bot],deq[bot+1])))<0) bot++;
106     if(bot==top) return;
107     cnt=0;
108     for(int i=bot;i<top;i++) p[++cnt]=getpoint(deq[i],deq[i+1]);
109     if(top-1>bot) p[++cnt]=getpoint(deq[bot],deq[top]);
110 }
111 
112 inline double getarea()
113 {
114     double res=0.0;
115     p[cnt+1]=p[1];
116     for(int i=1;i<=cnt;i++) res+=cross(o,p[i],p[i+1]);
117     return res;
118 }
119 
120 inline void go()
121 {
122     getcut();
123     printf("%.1lf\n",fabs(getarea())*0.5);
124 }
125 
126 int main()
127 {
128     while(scanf("%d",&n)!=EOF) read(),go();
129     return 0;
130 }
没有人能阻止我前进的步伐，除了我自己！