求解两个多边形公共部分面积问题
贝蒂喜欢剪纸，有两个新剪出的凸多边形需要粘在一起，她打算用糨糊涂抹两张剪纸的共同区域，请帮忙求出两个多边形的公共部分的面积。
输入描述：输入由两部分组成，每个部分的第一行是一个3~30的整数，指定多边形的顶点数，紧接的行指出多边形的顶点的坐标（由两个实数构成）。实数的小数部分包含6个数字，其绝对值低于1000，所有顶点按顺时针方向给出。
输出描述：输出一个实数（含两位小数），表示两个多边形的公共部分的面积。
输入样例
4
1.500000 -0.500000
-0.500000 1.500000
1.500000 3.500000
3.500000 1.500000
样例输出
7.00
解决方案详述，代码，思路，参考文献
如果满意，请采纳一下，谢谢
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 60 + 5;
const double eps = 1e-8;
int sgn(double x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator + (const Point& rhs) const { return Point(x + rhs.x, y + rhs.y); }
Point operator - (const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); }
Point operator * (double k) const { return Point(x * k, y * k); }
bool operator < (const Point& rhs) const { return sgn(y - rhs.y) < 0 || (sgn(y - rhs.y) == 0 && sgn(x - rhs.x) < 0); }
};
double cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
struct Line {
Point a, b;
Line() {}
Line(const Point& a, const Point& b) : a(a), b(b) {}
int orientation(const Point& p) {
double c = cross(b-a, p-a);
if (c < -eps) return -1; // 逆时针
else if (c > eps) return 1; // 顺时针
else return 0; // 共线
}
bool onLeft(const Point& p) {
return orientation(p) > 0;
}
Point intersect(const Line& rhs) {
Point da = b-a, db = rhs.b-rhs.a;
Point p = a + da * (cross(db, rhs.a-a) / cross(db, da));
return p;
}
};
int n, m;
vector<Point> P[maxn], Q[maxn];
vector<Line> H[maxn];
void intersection(const vector<Point>& P, const vector<Point>& Q, vector<Point>& R);
double polygon_area(vector<Point>& P);
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
P[i].resize(4);
for (int j = 0; j < 4; j++) {
cin >> P[i][j].x >> P[i][j].y;
}
}
cin >> m;
for (int i = 1; i <= m; i++) {
Q[i].resize(4);
for (int j = 0; j < 4; j++) {
cin >> Q[i][j].x >> Q[i][j].y;
}
}
// 求解两个凸多边形的交集
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
H[j].clear();
intersection(P[i], Q[j], H[j]);
}
H[0].clear(); // 记得清除这条边，否则用于求面积时会影响结果
for (int j = 1; j <= m; j++) {
for (size_t k = 0; k < H[j].size(); k++) {
H[0].push_back(H[j][k]);
}
}
P[i].swap(H[0]); // P[i] 中存储了两个多边形的交集
}
// 计算两个凸多边形的面积
double S1 = 0, S2 = 0;
for (int i = 1; i <= n; i++) {
S1 += polygon_area(P[i]);
}
for (int i = 1; i <= m; i++) {
S2 += polygon_area(Q[i]);
}
printf("%.2lf", S2 - S1);
return 0;
}
void intersection(const vector<Point>& P, const vector<Point>& Q, vector<Point>& R) {
// 将 P 中的顶点加入到矩形边界 Q 中（如果顶点都在矩形内部就不用加了）
bool inside = true;
for (size_t i = 0; i < P.size(); i++) {
if (Q[0].x <= P[i].x && P[i].x <= Q[2].x && Q[0].y <= P[i].y && P[i].y <= Q[2].y) {
inside = false;
break;
}
}
if (!inside) {
R.resize(P.size());
for (size_t i = 0; i < P.size(); i++) {
R[i] = P[i];
}
for (int i = 0; i < 4; i++) {
Line l(Q[i], Q[(i+1)%4]);
for (size_t j = 0; j < P.size(); j++) {
if (l.onLeft(P[j]) && !l.onLeft(P[(j+1)%P.size()])) {
R.push_back(l.intersect(Line(P[j], P[(j+1)%P.size()])));
}
else if (!l.onLeft(P[j]) && l.onLeft(P[(j+1)%P.size()])) {
R.push_back(l.intersect(Line(P[j], P[(j+1)%P.size()])));
}
}
}
}
}
double polygon_area(vector<Point>& P) {
double S = 0;
for (int i = 1; i < P.size() - 1; i++) {
S += cross(P[i]-P[0], P[i+1]-P[0]);
}
return S / 2;
}