#define MAXN 501
const double PI = acos(-1.00);
const double eps = 1e-6;
struct TPoint
{
double x,y;
};
struct TPoint operator-(TPoint a,TPoint b)
{
a.x-=b.x;
a.y-=b.y;
return a;
}
int sign(double d)
{
if(fabs(d) < eps) return 0;
return (d > 0) ? 1 : -1;
}
double cross(const TPoint & a, const TPoint & b)
{ return (a.x * b.y - a.y * b.x); }
//********
double cross(const TPoint & a, const TPoint & b, const TPoint & c)
{ return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }
//**************
TPoint seg_inter_pnt(TPoint & a, TPoint & b, TPoint & c, TPoint & d)
{
double s1 = cross(a, b, c), s2 = cross(a, b, d);
TPoint tmp;
tmp.x = (c.x * s2 - d.x * s1) / (s2 - s1);
tmp.y = (c.y * s2 - d.y * s1) / (s2 - s1);
return tmp;
}
//************8888
double area_poly(TPoint p[], int n)
{
double res = 0; p[n] = p[0];
for(int i = 0;i < n;++ i) res += cross(p[i], p[i+1]);
return fabs(res)/2.00;
}
//**************两个凸包的并
double convex_poly_inter_area(TPoint p1[], TPoint p2[], int n1, int n2)
{
TPoint tmp[MAXN];
int tn, i = 0, j, k, next, now;
p1[n1] = p1[0]; p2[n2] = p2[0];
for(i = 0;i < n1 && n2 > 2;++ i) {
now = sign(cross(p1[i+1] - p1[i], p2[0] - p1[i+1]));
for(j = tn = 0;j < n2;++ j, now = next) {
if(now >= 0) tmp[tn++] = p2[j];
next = sign(cross(p1[i+1] - p1[i], p2[j+1] - p1[i+1]));
if(now * next < 0)
tmp[tn++] = seg_inter_pnt(p1[i], p1[i+1], p2[j], p2[j+1]);
}
for(j = 0;j < tn;++ j) p2[j] = tmp[j];
n2 = tn; p2[n2] = p2[0];
}
if(n2 < 3) return 0.00;
return area_poly(p2, n2);
}
//********两个简单多边形的并
double simple_polygon_inter_area(TPoint p1[], int n1, TPoint p2[], int n2)
{
TPoint tp1[10]={0}, tp2[10]={0};
double ret = 0.00, flag, flag0;
for(int i = 0;i < n1;++ i) {
tp1[1] = p1[i]; tp1[2] = p1[i+1]; flag0 = 1.00;
if(cross(tp1[1] - tp1[0], tp1[2] - tp1[1]) < -eps)
flag0 = -1.00, swap(tp1[1], tp1[2]);
for(int j = 0;j < n2;++ j) {
tp2[1] = p2[j]; tp2[2] = p2[j+1]; flag = flag0;
if(cross(tp2[1] - tp2[0], tp2[2] - tp2[1]) < -eps)
flag *= -1.00, swap(tp2[1], tp2[2]);
ret += flag * convex_poly_inter_area(tp1, tp2, 3, 3);
}
}
return ret;
} |