ecnu1624求交集多边形面积

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 10000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x=,double y = ):x(x),y(y) {}
} p[N],q[N],ch[N],chh[N];
typedef point pointt;
point operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
double getarea(point p[],int n)
{
int i;
double area = ;
for(i = ; i < n-; i++)
area+=cross(p[i]-p[],p[i+]-p[]);
area = fabs(area)/;
return area;
}
bool PtInPolygon (point p, point ptPolygon[], int nCount)
{
int i,nCross = ;
for(i = ; i< nCount ; i++)
{
point p1 = ptPolygon[i];
point p2 = ptPolygon[(i+)%nCount];
if(dcmp(p1.y-p2.y)==) continue;
if(dcmp(p.y-min(p1.y,p2.y))<) continue;
if(dcmp(p.y-max(p1.y,p2.y))>=) continue;
double x = (double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;
if(x>p.x) nCross++;
}
return (nCross % == );
}
bool segprointer(point a1,point a2,point b1,point b2)
{
double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1);
double c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<&&dcmp(c3)*dcmp(c4)<;
}
bool intersection1(point p1, point p2, point p3, point p4, point& p) // 直线相交
{
double a1, b1, c1, a2, b2, c2, d;
a1 = p1.y - p2.y;
b1 = p2.x - p1.x;
c1 = p1.x*p2.y - p2.x*p1.y;
a2 = p3.y - p4.y;
b2 = p4.x - p3.x;
c2 = p3.x*p4.y - p4.x*p3.y;
d = a1*b2 - a2*b1;
if (!dcmp(d)) return false;
p.x = (-c1*b2 + c2*b1) / d;
p.y = (-a1*c2 + a2*c1) / d;
return true;
}
double mul(point p0,point p1,point p2)
{
return cross(p1-p0,p2-p0);
} bool cmp(point a,point b)
{
if(dcmp(mul(ch[],a,b))==)
return dis(a-ch[])<dis(b-p[]);
else
return dcmp(mul(ch[],a,b))>;
}
bool cmpp(point a,point b)
{
if(dcmp(a.x-b.x)==) return a.y<b.y;
return a.x<b.x;
}
int main()
{
int n,m,i,j;
while(scanf("%d",&n)!=EOF)
{ for(i = ; i < n ; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
p[n] = p[];
scanf("%d",&m);
for(i = ; i < m; i++)
scanf("%lf%lf",&q[i].x,&q[i].y);
q[m] = q[];
int g = ;
for(i = ; i < n ; i ++)
{
if(PtInPolygon(p[i],q,m))
ch[g++] = p[i];
}
for(i = ; i < m ; i ++)
{
if(PtInPolygon(q[i],p,n))
ch[g++] = q[i];
}
for(i = ; i < n; i++)
{
for(j = ; j < m ; j++)
{
if(segprointer(p[i],p[i+],q[j],q[j+])==) continue;
point pp;
if(!intersection1(p[i],p[i+],q[j],q[j+],pp))continue;
ch[g++] = pp;
}
}
double ans = ;//getarea(p,n)+getarea(q,m);
if(g==)
ans = ;
else
{
int k = ,o=;
sort(ch,ch+g,cmpp);
chh[o++] = ch[];
for(i = ; i < g; i++)
if(dcmp(ch[i].x-ch[i-].x)==&&dcmp(ch[i].y-ch[i-].y)==)
continue;
else chh[o++] = ch[i];
g = o;
for(i = ; i < g ; i ++)
{
if(dcmp(chh[i].y-chh[k].y)<||(dcmp(chh[i].y-chh[k].y)==&&dcmp(chh[i].x-chh[k].x)<))
k = i;
}
if(k!=) swap(chh[k],chh[]);
sort(chh+,chh+g,cmp);
ans = getarea(chh,g);
}
printf("%.2f\n",ans);
}
return ;
}