1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 510 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     double x,y; 20     point(double x=0,double y=0):x(x),y(y) {} //构造函数 方便代码编写 21 }p[N],q[N]; 22 typedef point pointt; 23 pointt operator + (point a,point b) 24 { 25     return point(a.x+b.x,a.y+b.y); 26 } 27 pointt operator - (point a,point b) 28 { 29     return point(a.x-b.x,a.y-b.y); 30 } 31 int dcmp(double x) 32 { 33     if(fabs(x)<eps) return 0; 34     else return x<0?-1:1; 35 } 36 bool operator == (const point &a,const point &b) 37 { 38     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; 39 } 40 double cross(point a,point b) 41 { 42     return a.x*b.y-a.y*b.x; 43 } 44 double Polyarea(point p[],int n) 45 { 46     if(n<3) return 0; 47     double area = 0; 48     for(int i = 0 ; i < n ; i++) 49     area+=cross(p[i],p[i+1]); 50     return fabs(area)/2; 51 } 52 //double Polyarea(point p[], int n) 53 //{ 54 //    if(n < 3) return 0.0; 55 //    double s = p[0].y * (p[n - 1].x - p[1].x); 56 //    p[n] = p[0]; 57 //    for(int i = 1; i < n; ++ i) 58 //        s += p[i].y * (p[i - 1].x - p[i + 1].x); 59 //    return fabs(s * 0.5); 60 //} 61 bool intersection1(point p1, point p2, point p3, point p4, point& p)      // 直线相交 62 { 63     double a1, b1, c1, a2, b2, c2, d; 64     a1 = p1.y - p2.y; 65     b1 = p2.x - p1.x; 66     c1 = p1.x*p2.y - p2.x*p1.y; 67     a2 = p3.y - p4.y; 68     b2 = p4.x - p3.x; 69     c2 = p3.x*p4.y - p4.x*p3.y; 70     d = a1*b2 - a2*b1; 71     if (!dcmp(d))    return false; 72     p.x = (-c1*b2 + c2*b1) / d; 73     p.y = (-a1*c2 + a2*c1) / d; 74     return true; 75 } 76  77 double convexpolygon(point p[],point q[],int n,int m) 78 { 79     int i,j; 80     point ch[20],cnt[20]; 81     p[n] = p[0],q[m] = q[0]; 82     memcpy(ch,q,sizeof(point)*(m+1)); 83     int f2,g = 0 ; 84     for(i = 0 ;i < n; i++) 85     { 86         int f1 = dcmp(cross(p[i+1]-p[i],ch[0]-p[i])); 87         g = 0 ; 88         for(j = 0 ;j < m; j++,f1 = f2) 89         { 90             if(f1>=0) cnt[g++] = ch[j]; 91             f2 = dcmp(cross(p[i+1]-p[i],ch[j+1]-p[i])); 92             if((f1^f2)==-2) 93             { 94                 point pp; 95                 intersection1(p[i],p[i+1],ch[j],ch[j+1],pp); 96                 cnt[g++] = pp; 97             } 98         } 99         cnt[g] = cnt[0];100         memcpy(ch,cnt,sizeof(point)*(g+1));101         m = g;102     }103     return Polyarea(ch,g);104 }105 double solve(point p[],point q[],int n,int m)106 {107     int i,j;108     double area = 0;109     point tp[10],tq[10];110     tp[0] = p[0];tq[0] = q[0];111     for(i = 1 ;i < n-1; i++)112     {113         int k1 = dcmp(cross(p[i]-p[0],p[i+1]-p[0]));114         tp[1] = p[i],tp[2] = p[i+1];115         if(k1 < 0) swap(tp[1],tp[2]);116 117         for(j = 1 ;j < m-1 ;j++)118         {119             tq[1] = q[j],tq[2] = q[j+1];120             int k2 = dcmp(cross(q[j]-q[0],q[j+1]-q[0]));121             if(k2<0) swap(tq[1],tq[2]);122 123             area+=convexpolygon(tp,tq,3,3)*k1*k2;124         }125     }126     return Polyarea(p,n)+Polyarea(q,m)-area;127 }128 int main()129 {130     int n,m,i;131     while(scanf("%d%d",&n,&m)!=EOF)132     {133         for(i = 0; i < n ;i++)134         {135             scanf("%lf%lf",&p[i].x,&p[i].y);136         }137         for(i = 0; i < m; i++)138         {139             scanf("%lf%lf",&q[i].x,&q[i].y);140         }141         p[n] = p[0],q[m] = q[0];142         double ans = solve(p,q,n,m);143         printf("%.2f\n",ans);144     }145     return 0;146 }