链接：https://ac.nowcoder.com/acm/contest/1112/J
来源：牛客网
题目描述
Bobo 有一个三角形和一个矩形，他想求他们交的面积。
具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1,y1,x2,y2,x3,y3,x4,y4 描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1,y1),(x1,y2),(x2,y1)，
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3,y3),(x3,y4),(x4,y4),(x4,y3).
具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1,y1,x2,y2,x3,y3,x4,y4 描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1,y1),(x1,y2),(x2,y1)，
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3,y3),(x3,y4),(x4,y4),(x4,y3).
输入描述:
输入包含不超过 30000 组数据。
每组数据的第一行包含 4 个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2 (x1≠x2,y1≠y2x_1 \neq x_2, y_1 \neq y_2x1=x2,y1=y2).
第二行包含 4 个整数 x3,y3,x4,y4x_3, y_3, x_4, y_4x3,y3,x4,y4 (x3<x4,y3<y4x_3 < x_4, y_3 < y_4x3<x4,y3<y4).
(0≤xi,yi≤1040 \leq x_i, y_i \leq 10^40≤xi,yi≤104)
输出描述:
对于每组数据，输出一个实数表示交的面积。绝对误差或相对误差小于 10−610^{-6}10−6 即认为正确。
示例3
输出
439744.13967527
AC代码：
/*
* 多边形的交，多边形的边一定是要按逆时针方向给出
* 还要判断是凸包还是凹包，调用相应的函数
* 面积并，只要和面积减去交即可
*/
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
const double eps = 1e-;
int dcmp(double x)
{
if(x > eps) return ;
return x < -eps ? - : ;
}
struct Point
{
double x, y;
};
double cross(Point a,Point b,Point c) ///叉积
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
Point intersection(Point a,Point b,Point c,Point d)
{
Point p = a;
double t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));
p.x +=(b.x-a.x)*t;
p.y +=(b.y-a.y)*t;
return p;
}
//计算多边形面积
double PolygonArea(Point p[], int n)
{
if(n < ) return 0.0;
double s = p[].y * (p[n - ].x - p[].x);
p[n] = p[];
for(int i = ; i < n; ++ i)
s += p[i].y * (p[i - ].x - p[i + ].x);
return fabs(s * 0.5);
}
double CPIA(Point a[], Point b[], int na, int nb)//ConvexPolygonIntersectArea
{
Point p[], tmp[];
int tn, sflag, eflag;
a[na] = a[], b[nb] = b[];
memcpy(p,b,sizeof(Point)*(nb + ));
for(int i = ; i < na && nb > ; i++)
{
sflag = dcmp(cross(a[i + ], p[],a[i]));
for(int j = tn = ; j < nb; j++, sflag = eflag)
{
if(sflag>=) tmp[tn++] = p[j];
eflag = dcmp(cross(a[i + ], p[j + ],a[i]));
if((sflag ^ eflag) == -)
tmp[tn++] = intersection(a[i], a[i + ], p[j], p[j + ]); ///求交点
}
memcpy(p, tmp, sizeof(Point) * tn);
nb = tn, p[nb] = p[];
}
if(nb < ) return 0.0;
return PolygonArea(p, nb);
}
double SPIA(Point a[], Point b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数
{
int i, j;
Point t1[], t2[];
double res = , num1, num2;
a[na] = t1[] = a[], b[nb] = t2[] = b[];
for(i = ; i < na; i++)
{
t1[] = a[i-], t1[] = a[i];
num1 = dcmp(cross(t1[], t1[],t1[]));
if(num1 < ) swap(t1[], t1[]);
for(j = ; j < nb; j++)
{
t2[] = b[j - ], t2[] = b[j];
num2 = dcmp(cross(t2[], t2[],t2[]));
if(num2 < ) swap(t2[], t2[]);
res += CPIA(t1, t2, , ) * num1 * num2;
}
}
// res=fabs(res);
return res;
}
Point p1[maxn], p2[maxn];
int n1, n2;
int main()
{
int x1,x2,x3,x4,y1,y2,y3,y4;
while(~ scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){ scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
p1[].x = x1;p1[].y = y1;
p1[].x = x1;p1[].y = y2;
p1[].x = x2;p1[].y = y1; p2[].x = x3;p2[].y = y3;
p2[].x = x3;p2[].y = y4;
p2[].x = x4;p2[].y = y4;
p2[].x = x4;p2[].y = y3;
double s1 = SPIA(p1,p2,,);
printf("%.8f\n",fabs(s1));
}
return ;
}