80pts求助
查看原帖
80pts求助
230738
SZbr楼主2021/12/12 16:09
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<utility>
#include<set>
#pragma warning(disable:4996)
using namespace std;
#define int long long
#define Pair pair<long long,long long>
int n, cnt;
Pair p[1010][3];
set<int> sx;
int xt[1010];
int ans;
struct yzh
{
	int t, e;
}yi[10010];
int tot;
int pre[100010];
bool cmp(yzh a, yzh b) {
	return a.t < b.t;
}
void add(int l,int r) {
	tot = 0;
	//cout << l << " " << r << endl;
	for (int j = 1; j <= n; ++j) {
		if (p[j][0].first <= l && p[j][1].first >= r) {
			yi[++tot].t = p[j][0].second;
			yi[tot].e = p[j][1].second;
		}
	}
	sort(yi + 1, yi + tot + 1, cmp);
	int maxn = -0x7f7f7f7f;
	int k = r - l;
	for (int j = 1; j <= tot; ++j) {
		if (maxn <= yi[j].e) {
			ans += (k * (yi[j].e - max(maxn, yi[j].t)));
		}
		maxn = max(maxn, yi[j].e);
	}
}
signed main() {
	//scanf("%lld", &n);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		//scanf("%lld%lld%lld%lld", &p[i][0].first, &p[i][0].second, &p[i][1].first, &p[i][1].second);
		cin >> p[i][0].first >> p[i][0].second >> p[i][1].first >> p[i][1].second;
		swap(p[i][0].second, p[i][1].second);
		sx.insert(p[i][0].first);
		sx.insert(p[i][1].first);
	}
	for (auto it : sx) {
		xt[++cnt] = it;
	}
	for (int i = 1; i < cnt; ++i) {
		int l = xt[i], r = xt[i + 1];
		add(l, r);
	}
	cout << ans;
	return 0;
}
2021/12/12 16:09
加载中...