之前怀疑是不是我的扫描线和其他人的不一样
// Problem: 过度种植
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2034/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
/*
Created by YuXiao
Nothing to say.
*/
#define YuXiao() cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
int n;
PII l[N], r[N];
PII q[N];
vector<int> xs;
int range_area(int a, int b)
{
int cnt = 0;
for (int i = 0; i < n; i ++)
if (l[i].x <= a && r[i].x >= b)
q[cnt ++] = {l[i].y, r[i].y};
if (!cnt) return 0;
sort(q, q + cnt);
int res = 0;
int st = q[0].x, ed = q[0].y;
for (int i = 1; i < cnt; i ++)
if (q[i].x <= ed) ed = max(ed, q[i].y);
else
{
res += ed - st;
st = q[i].x, ed = q[i].y;
}
res += ed - st;
return res * (b - a);
}
int main()
{
YuXiao();
cin >> n;
for (int i = 0; i < n; i ++)
{
cin >> l[i].x >> r[i].y >> r[i].x >> l[i].y;
xs.push_back(l[i].x), xs.push_back(r[i].x);
}
sort(xs.begin(), xs.end());
int res = 0;
for (int i = 0; i < xs.size() - 1; i ++)
if (xs[i] != xs[i + 1])
res += range_area(xs[i], xs[i + 1]);
cout << res << endl;
return 0;
}
写的好好看!
棒耶耶!