가장 넓은 그룹의 넓이를 구하는 문제이다.
============================================================================
직사각형 한 개당 너비와 높이가 최대 500이므로 직사각형 각각의 grid를 이용해서 풀기는 어렵다.
직사각형의 선분을 이용해보자!
모든 직사각형의 x,y좌표들을 압축을 해주고 y좌표에는 직사각형의 너비를, x좌표에는 직사각형의
높이를 넣어준다.
선분이 교차하는 부분이 있다면 같은 그룹이다.
선분이 교차하는것은 sweeping을 하면서 판별해 주고 union find로 같은그룹으로 묶어주면 해결된다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
typedef long long ll;
struct Rect {
int x, y, w, h;
};
int n;
bool visit[MAXN];
Rect rect[MAXN];
int par[MAXN];
ll sze[MAXN];
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (sze[u] > sze[v]) swap(u, v);
sze[v] += sze[u];
sze[u] = 0;
par[u] = v;
}
vector<ll> xpos, ypos;
set<pair<ll,pair<ll, int>>> savex[100005], savey[100005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &rect[i].x, &rect[i].y, &rect[i].w, &rect[i].h);
sze[i] = rect[i].w*rect[i].h;
par[i] = i;
xpos.push_back(rect[i].x);
xpos.push_back((ll)rect[i].x + (ll)rect[i].w);
ypos.push_back(rect[i].y);
ypos.push_back((ll)rect[i].y + (ll)rect[i].h);
}
sort(xpos.begin(), xpos.end());
sort(ypos.begin(), ypos.end());
xpos.erase(unique(xpos.begin(), xpos.end()), xpos.end());
ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
for (int i = 1; i <= n; i++) {
int idx = lower_bound(xpos.begin(), xpos.end(), rect[i].x) - xpos.begin();
savex[idx].insert({ rect[i].y, {-rect[i].h, i} });
idx = lower_bound(xpos.begin(), xpos.end(), (ll)rect[i].x + (ll)rect[i].w) - xpos.begin();
savex[idx].insert({ rect[i].y, {-rect[i].h, i} });
idx = lower_bound(ypos.begin(), ypos.end(), rect[i].y) - ypos.begin();
savey[idx].insert({ rect[i].x, {-rect[i].w, i} });
idx = lower_bound(ypos.begin(), ypos.end(), (ll)rect[i].y + (ll)rect[i].h) - ypos.begin();
savey[idx].insert({ rect[i].x, {-rect[i].w ,i} });
}
for (int i = 0; i < xpos.size(); i++) {
auto curr = savex[i].begin();
auto nxt = curr;
ll cover = (*curr).first - (*curr).second.first;
while (++nxt != savex[i].end()) {
int idx = (*curr).second.second, xdi = (*nxt).second.second;
if ((*nxt).first <= cover) {
merge(idx, xdi);
}
cover = max(cover, (*nxt).first - (*nxt).second.first);
curr = nxt;
}
}
for (int i = 0; i < ypos.size(); i++) {
auto curr = savey[i].begin();
auto nxt = curr;
ll cover = (*curr).first - (*curr).second.first;
while (++nxt != savey[i].end()) {
int idx = (*curr).second.second, xdi = (*nxt).second.second;
if ((*nxt).first <= cover) {
merge(idx, xdi);
}
cover = max(cover, (*nxt).first - (*nxt).second.first);
curr = nxt;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, sze[find(i)]);
printf("%lld\n", ans);
return 0;
}
| cs |
