救命
查看原帖
救命
241115
guzzqq楼主2021/7/21 19:26
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define repp(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
int N;
int x11[1011], y11[1011];
int x2[1011], y2[1011];
int a[4011], c[4011];
int delta[4011][4011];
int f[4011][4011];
int cnta, cntc;
long long ans;
int main(){
	scanf("%d",&N);
	rep(i, 1, N){
		scanf("%d%d%d%d",&x11[i], &y11[i], &x2[i], &y2[i]);
		x11[i] += 1e8;y11[i] += 1e8;x2[i] += 1e8;y2[i] += 1e8;
		a[++cnta] = x11[i];a[++cnta] = y11[i];a[++cnta] = x2[i];a[++cnta] = y2[i];
	}
	sort(a + 1, a + cnta + 1);
	a[0] = -6666666666;
	rep(i, 1, 4 * N)if(a[i] != a[i - 1])c[++cntc] = a[i];
	rep(i, 1, N){
		int xx1 = lower_bound(c + 1, c + cntc + 1, x11[i]) - c;
		int yy1 = lower_bound(c + 1, c + cntc + 1, y11[i]) - c;
		int xx2 = lower_bound(c + 1, c + cntc + 1, x2[i]) - c;
		int yy2 = lower_bound(c + 1, c + cntc + 1, y2[i]) - c;
		delta[xx1][yy1]++;
		delta[xx2 + 1][yy1]--;
		delta[xx1][yy2 - 1]--;
		delta[xx2 + 1][yy2 - 1]++;
	}
	repp(i, cntc, 1){
		rep(j, 1, cntc){
			delta[i][j] += (delta[i + 1][j] + delta[i][j - 1] - delta[i + 1][j - 1]);
		}
	}
	repp(i, cntc, 2){
		rep(j, 1, cntc){
			if(delta[i][j] > 0 && delta[i - 1][j + 1] > 0){
				ans += (long long)((c[i] - c[i - 1]) * (c[j + 1] - c[j]));
				continue;
			}
			if(delta[i][j] > 0){
				ans++;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}
2021/7/21 19:26
加载中...