离散化的一个题 终于会了 借鉴了一下大佬的题解(一模一样)
大佬题解链接如下
题解
题目链接
格子染色
有自己的一些理解
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
struct Node
{
int k, l, r;
bool operator < (const Node & W) const
{
if (k != W.k) return k < W.k;
else if (l != W.l) return l < W.l;
else if (r != W.r) return r < W.r;
}
};
int n;
LL cnt;
vector<Node> cols, rows;
void merge(vector<Node> &segs)
{
sort(segs.begin(), segs.end());
vector<Node> res;
int st, ed, k;
st = ed = k = -2e9;
for (auto seg : segs)
{
if (seg.k == k)
{
if (ed < seg.l)
{
if(st != -2e9) res.push_back({k, st, ed}), cnt += ed - st + 1;
st = seg.l, ed = seg.r;
}
else ed = max(ed, seg.r);
}
else
{
if (st != -2e9)
{
cnt += ed - st + 1;
res.push_back({k, st, ed});
}
k = seg.k, st = seg.l, ed = seg.r;
}
}
if(st != -2e9) res.push_back({k, st, ed}), cnt += ed - st + 1;
segs = res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
while (n--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) cols.push_back({x1, min(y1, y2), max(y1, y2)});
else rows.push_back({y1, min(x1, x2), max(x1, x2)});
}
merge(cols), merge(rows);
for(auto col : cols)
for(auto row : rows)
if(row.k >= col.l && row.k <= col.r && row.r >= col.k && row.l <= col.k) cnt --;
cout << cnt << endl;
return 0;
}