hdu3060Area2(任意多边形相交面积)

  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 }