poj2451Uyuw's Concert(半平面交）

链接

逆时针给出线段，如果模板是顺时针的修改下系数的符号进行平面交即可。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 20100

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int m;

 int cCnt,curCnt;

 struct point

 {

     double x,y;

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

 };

 point points[N],p[N],q[N];

 void getline(point x,point y,double &a,double &b,double   &c)

 {

     a = x.y - y.y;

     b = y.x - x.x;

     c = x.x * y.y-y.x * x.y;

 }

 void initial()

 {

     for(int i = ; i <= m; ++i)p[i] = points[i];

     p[m+] = p[];

     p[] = p[m];

     cCnt = m;

 }

 point intersect(point x,point y,double a,double b,double c)

 {

     double u = fabs(a * x.x + b * x.y + c);

     double v = fabs(a * y.x + b * y.y + c);

     point pt;

     pt.x=(x.x * v + y.x * u) / (u + v);

     pt.y=(x.y * v + y.y * u) / (u + v);

     return  pt;

 }

 void cut(double a,double b ,double c)

 {

     curCnt = ;

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

     {

         if(a*p[i].x + b*p[i].y + c >= )q[++curCnt] = p[i];

         else

         {

             if(a*p[i-].x + b*p[i-].y + c > )

                 q[++curCnt] = intersect(p[i],p[i-],a,b,c);

             if(a*p[i+].x + b*p[i+].y + c > )

                 q[++curCnt] = intersect(p[i],p[i+],a,b,c);

         }

     }

     for(int i = ; i <= curCnt; ++i)p[i] = q[i];

     p[curCnt+] = q[];

     p[] = p[curCnt];

     cCnt = curCnt;

 }

 void solve()

 {

     double area = ;

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

         area += p[i].x * p[i + ].y - p[i + ].x * p[i].y;

     area = fabs(area / 2.0);

     printf("%.1f\n",area);

 }

 void GuiZhengHua()

 {

     //规整化方向，逆时针变顺时针，顺时针变逆时针

     for(int i = ; i < (m+)/; i ++)

         swap(points[i], points[m-i]);

 }

 int main()

 {

     points[] = point(,);

     points[] = point(,);

     points[] = point(,);

     points[] = point(,);

     points[] = p[];

     int n,i;

     while(scanf("%d",&n)!=EOF)

     {

         m = ;

         initial();

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

         {

             double a,b,c;

             getline(points[i],points[i+],a,b,c);

             cut(a,b,c);

         }

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

         {

             point p1,p2;

             scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);

             double a,b,c;

             getline(p1,p2,a,b,c);

             cut(a,b,c);

         }

        // m = 2*n+4;

         //GuiZhengHua();

         //points[m+1] = points[1];

         solve();

     }

     return ;

 }