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 ;
}