计算几何|【计算几何】图形面积计算几何|acm竞赛

【计算几何】图形面积 【计算几何|【计算几何】图形面积】时间限制: 1 Sec 内存限制: 128 MB

题目描述

桌面上放了N N N 个平行于坐标轴的矩形，这N N N 个矩形可能有互相覆盖的部分，求它们组成的图形的面积。

输入

输入第一行为一个数N ( 1 ≤ N ≤ 100 ) N(1≤N≤100) N(1≤N≤100)，表示矩形的数量。下面N N N 行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为– 1 0 8 –10^8 –108到 1 0 8 10^8 108之间的整数。

输出

输出只有一行，一个整数，表示图形的面积。

样例输入

3 1 1 4 3 2 -1 3 2 4 0 5 2

样例输出

10

#pragma GCC optimize(3,"Ofast","inline") #include #include #include #include #include #include #include #include #include #include using namespace std; #define ls (rt<<1) #define rs (rt<<1|1) typedef long long ll; template inline void read(T &x) { x = 0; static int p; p = 1; static char c; c = getchar(); while (!isdigit(c)) { if (c == '-')p = -1; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); } x *= p; } template inline void print(T x) { if (x<0) { x = -x; putchar('-'); } static int cnt; static int a[50]; cnt = 0; do { a[++cnt] = x % 10; x /= 10; } while (x); for (int i = cnt; i >= 1; i--)putchar(a[i] + '0'); puts(""); } const double pi=acos(-1); const double eps=1e-6; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int maxn = 1010; int n; __int128 x1[maxn],x2[maxn],yy[maxn],y2[maxn]; __int128 h[maxn<<1],l[maxn<<1]; int t,T; inline void work() { read(n); for (int i = 1; i <= n; ++i) { read(x2[i]); read(y2[i]); read(x1[i]); read(yy[i]); h[++t] = x1[i]; h[++t] = x2[i]; l[++T] = yy[i]; l[++T] = y2[i]; } sort(h + 1, h + 1 + t); t = unique(h + 1, h + t + 1) - (h + 1); sort(l + 1, l + 1 + T); T = unique(l + 1, l + T + 1) - (l + 1); __int128 ans = 0; for (int i = 1; i <= t; ++i) { for (int j = 1; j <= T; ++j) { for (int k = 1; k <= n; ++k) { if (h[i] < x1[k] && h[i] >= x2[k] && l[j] < yy[k] && l[j] >= y2[k]) { ans += (h[i + 1] - h[i]) * (l[j + 1] - l[j]); break; } } } } print(ans); } int main() { //freopen("1.txt","r",stdin); int T = 1; //read(T); while (T--) { work(); } return 0; }