AcWing 759. 格子染色
原题链接
中等
作者:
AKACC
,
2022-03-01 01:20:25
,
所有人可见
,
阅读 155
题目描述
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// typedef pair<int, int> PII;
const int N = 100010;
long long counts = 0;
struct Node
{
int l;
int r;
int k;
};
int fun(Node a, Node b)
{
if(a.k != b.k)
{
return a.k < b.k;
}
if(a.l != b.l)
{
return a.l < b.l;
}
else
{
return a.r < b.r;
}
}
void merge(vector<Node> &data)
{
sort(data.begin(),data.end(), fun);
int k = -1e9-1;
int start = -1e9-1;
int end = -1e9-1;
vector<Node> res;
Node tmp;
for(auto node : data)
{
if(k == node.k)
{
if(node.l > end)
{
tmp.l = start;
tmp.r = end;
tmp.k = k;
if(start > -1e9-1)
{
res.push_back(tmp);
counts += end - start + 1;
}
start = node.l;
end = node.r;
}
else
{
end = max(end, node.r);
}
}
else
{
tmp.l = start;
tmp.r = end;
tmp.k = k;
if(start > -1e9-1)
{
res.push_back(tmp);
counts += end - start + 1;
}
start = node.l;
end = node.r;
k = node.k;
}
}
if(start > -1e9-1)
{
tmp.l = start;
tmp.r = end;
tmp.k = k;
res.push_back(tmp);
counts += end - start + 1;
}
data = res;
return;
}
int main(void)
{
vector<Node> rows;
vector<Node> cols;
long long n, x1, y1, x2, y2;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
if(x1 == x2)
{
Node node;
node.k = x1;
node.l = min(y1, y2);
node.r = max(y1, y2);
rows.push_back(node);
}
else
{
Node node;
node.k = y1;
node.l = min(x1, x2);
node.r = max(x1, x2);
cols.push_back(node);
}
}
merge(rows);
// for(auto t : rows)
// {
// cout << t.k << " " << t.l << " " << t.r<<endl;
// }
// cout << "###"<<endl;
merge(cols);
// for(auto t : cols)
// {
// cout << t.k << " " << t.l << " " << t.r<<endl;
// }
for(auto row : rows)
{
for(auto col : cols)
{
if(row.k >= col.l && row.k <= col.r && col.k >= row.l && col.k <= row.r)
{
counts--;
}
}
}
cout << counts << endl;
return 0;
}