模板题
题意:给定两个凸多边形,求出合并后的面积,这个合并后的面积不包括重叠部分。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; const int maxn = 155; const int maxm = 155; const double eps = 1e-8; 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 = 0; for( int i=2;i<n;i++ ){ sum += xmult( p[1],p[i],p[i+1] ); } return -sum/2.0; }//面积,顺时针为正 void cut( double a,double b,double c,int &cnt ){ int temp = 0; for( int i=1;i<=cnt;i++ ){ if( a*res[i].x+b*res[i].y+c>-eps ){//>=0 tp[ ++temp ] = res[i]; } else{ if( a*res[i-1].x+b*res[i-1].y+c>eps ){ tp[ ++temp ] = Intersection( res[i-1],res[i],a,b,c ); } if( a*res[i+1].x+b*res[i+1].y+c>eps ){ tp[ ++temp ] = Intersection( res[i],res[i+1],a,b,c ); } } } for( int i=1;i<=temp;i++ ) res[i] = tp[i]; res[ 0 ] = res[ temp ]; res[ temp+1 ] = res[ 1 ]; cnt = temp; } int main(){ int m,n; while( scanf("%d",&n)==1,n ){ for( int i=1;i<=n;i++ ){ scanf("%lf%lf",&pnt1[i].x,&pnt1[i].y); } scanf("%d",&m); for( int i=1;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+1,pnt1+1+n ); } pnt1[ 0 ] = pnt1[ n ]; pnt1[ n+1 ] = pnt1[ 1 ]; if( sumArea2<eps ){ reverse( pnt2+1,pnt2+1+m ); } pnt2[ 0 ] = pnt2[ m ]; pnt2[ m+1 ] = pnt2[ 1 ]; for( int i=0;i<=n+1;i++ ){ res[i] = pnt1[i]; } int cnt = n; for( int i=1;i<=m;i++ ){ double a,b,c; Get_equation( pnt2[i],pnt2[i+1],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 0; }