GYM 101673 A - Abstract Art 多个一般多边形面积并

时间:2024-01-15 22:46:02

A - Abstract Art

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); struct Point {
double x, y;
Point(double x = , double y = ) : x(x), y(y) { } };
typedef Point Vector;
int dcmp(double x) {
if(fabs(x) < eps) return ;
else return x < ? - : ;
}
Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}
Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}
Point operator * (Vector A, double p) {return Point(A.x * p, A.y * p);}
Point operator / (Vector A, double p) {return Point(A.x / p, A.y / p);}
bool operator < (const Vector &A, const Vector &B) {return A.y < B.y || (A.y == B.y && A.x < B.x);}
bool operator == (const Vector &A, const Point &B) {return dcmp(A.x - B.x) == && dcmp(A.y - B.y) == ;}
double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}
double Length(Vector A) {return sqrt(Dot(A, A));}
double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Length(A) / Length(B));}
double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
double Area2(Point A, Point B, Point C) {return Cross(B - A, C - A);} double PolygonArea(vector<Point>& p) {
int n = p.size();
double area = ;
for(int i = ; i < n - ; i++)
area += Cross(p[i]-p[], p[i+]-p[]);
return fabs(area / );
} double Seg(Point O, Point A, Point B){
if(dcmp(B.x - A.x) == ) return (O.y - A.y) / (B.y - A.y);
return (O.x - A.x) / (B.x - A.x);
} double MultiPolyArea(vector<Point>* p, int n) {
double res=;
vector<pair<double, int>> s;
for(int i = ; i < n; i++) {
int sz = p[i].size();
for(int j = ; j < sz; j++){
s.clear();
s.push_back(mk(, ));
s.push_back(mk(, ));
Point a = p[i][j], b = p[i][(j+)%sz];
for(int k = ; k < n; k++){
if(i != k){
int sz2 = p[k].size();
for(int z = ; z < sz2; z++){
Point c = p[k][z], d = p[k][(z+)%sz2];
int c1 = dcmp(Cross(b-a, c-a));
int c2 = dcmp(Cross(b-a, d-a));
if(c1 == && c2 == ) {
if(dcmp(Cross(b-a, d-c))) {
s.push_back(mk(Seg(c, a, b), ));
s.push_back(mk(Seg(c, a, b), -));
}
} else {
double s1 = Cross(d-c, a-c), s2 = Cross(d-c, b-c);
if(c1 >= && c2 < ) s.push_back(mk(s1/(s1-s2), ));
else if(c1 < && c2 >= ) s.push_back(mk(s1/(s1-s2), -));
}
}
}
}
sort(s.begin(), s.end());
double pre = min(max(s[].fi, 0.0), 1.0), now, sum=;
int cov = s[].se;
for(int j = ; j < s.size(); j++) {
now = min(max(s[j].fi, 0.0), 1.0);
if(!cov) sum += now - pre;
cov += s[j].second;
pre = now;
}
res += Cross(a, b) * sum;
}
}
return fabs(res / );
} int n, m;
vector<Point> poly[]; int main() {
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &m);
poly[i].resize(m);
for(int j = ; j < m; j++) {
scanf("%lf%lf", &poly[i][j].x, &poly[i][j].y);
}
}
double ans1 = , ans2 = MultiPolyArea(poly, n);
for(int i = ; i < n; i++) ans1 += PolygonArea(poly[i]);
printf("%.12f %.12f\n", ans1, ans2);
return ;
} /*
*/