HDU1632+半平面交

模板题

题意：给定两个凸多边形，求出合并后的面积，这个合并后的面积不包括重叠部分。

 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 const int maxn = ;
 const int maxm = ;
 const double eps = 1e-;
 const double pi = acos(-1.0);
 struct Point{
     double x,y;
 };
 struct Line{
     Point a,b;
 };
 Point pnt1[ maxn ],res[ maxm ],pnt2[ maxn ],tp[ maxm ];
 double xmult( Point op,Point sp,Point ep ){
     return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
 }
 double dist( Point a,Point b ){
     return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
 }
 void Get_equation( Point p1,Point p2,double &a,double &b,double &c ){
     a = p2.y-p1.y;
     b = p1.x-p2.x;
     c = p2.x*p1.y-p1.x*p2.y;
 }//直线方程
 Point Intersection( Point p1,Point p2,double a,double b,double c ){
     double u = fabs( a*p1.x+b*p1.y+c );
     double v = fabs( a*p2.x+b*p2.y+c );
     Point tt;
     tt.x = (p1.x*v+p2.x*u)/(u+v);
     tt.y = (p1.y*v+p2.y*u)/(u+v);
     return tt;
 }//交点、按照三角比例求出交点
 double GetArea( Point p[],int n ){
     double sum = ;
     for( int i=;i<n;i++ ){
         sum += xmult( p[],p[i],p[i+] );
     }
     return -sum/2.0;
 }//面积，顺时针为正
 void cut( double a,double b,double c,int &cnt ){
     int temp = ;
     for( int i=;i<=cnt;i++ ){
         if( a*res[i].x+b*res[i].y+c>-eps ){//>=0
             tp[ ++temp ] = res[i];
         }
         else{
             if( a*res[i-].x+b*res[i-].y+c>eps ){
                 tp[ ++temp ] = Intersection( res[i-],res[i],a,b,c );
             }
             if( a*res[i+].x+b*res[i+].y+c>eps ){
                 tp[ ++temp ] = Intersection( res[i],res[i+],a,b,c );
             }
         }
     }
     for( int i=;i<=temp;i++ )
         res[i] = tp[i];
     res[  ] = res[ temp ];
     res[ temp+ ] = res[  ];
     cnt = temp;
 } int main(){
     int m,n;
     while( scanf("%d",&n)==,n ){
         for( int i=;i<=n;i++ ){
             scanf("%lf%lf",&pnt1[i].x,&pnt1[i].y);
         }
         scanf("%d",&m);
         for( int i=;i<=m;i++ ){
             scanf("%lf%lf",&pnt2[i].x,&pnt2[i].y);
         }
         double sumArea1,sumArea2,Area;
         sumArea1 = GetArea( pnt1,n );
         sumArea2 = GetArea( pnt2,m );
         if( sumArea1<eps ){
             reverse( pnt1+,pnt1++n );
         }
         pnt1[  ] = pnt1[ n ];
         pnt1[ n+ ] = pnt1[  ];
         if( sumArea2<eps ){
             reverse( pnt2+,pnt2++m );
         }
         pnt2[  ] = pnt2[ m ];
         pnt2[ m+ ] = pnt2[  ];
         for( int i=;i<=n+;i++ ){
             res[i] = pnt1[i];
         }
         int cnt = n;
         for( int i=;i<=m;i++ ){
             double a,b,c;
             Get_equation( pnt2[i],pnt2[i+],a,b,c );
             cut(a,b,c,cnt);
         }
         Area = GetArea( res,cnt );
         double ans = fabs(sumArea1)+fabs(sumArea2)-2.0*fabs(Area);
         printf("%8.2lf",ans);
     }
     puts("");
     return ;
 }