Live Archive 6889 : City Park
問題リンク : https://icpcarchive.ecs.baylor.edu/external/68/6889.pdf
問題概要 :
2次元平面上に1つ以上の長方形がそれぞれオーバーラップせずに置いてある
長方形の縦と横はそれぞれy軸とx軸に平行である
2つの長方形が辺または角で接しているとき、それらの長方形は同じグループに属する
2次元平面内の存在するグループのうち、長方形の面積の総和が最大のものをみつけ、その値を出力せよ
制約 :
長方形の数は高々50000
長方形の各辺の長さは最大500
解法 :
平面走査
長方形はオーバーラップしないので2次元平面上の1点に存在しうる最大の長方形の数は高々4つ
計算量は ( 50000 * 2 ) * 500 * 4 となる
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; const int MAX = 50010; struct Event { int x,ID; bool operator < ( const Event& e) const { return ( x != e.x ) ? x < e.x : ID < e.ID; } }; int par[MAX]; int find(int x){ if( x == par[x] ) return x; return par[x] = find(par[x]); } void unit(int x,int y){ x = find(x), y = find(y); if( x != y ) par[x] = y; } ll area[MAX],group_area[MAX]; int n,ys[MAX],ye[MAX]; vector<Event> events; void compressY(){ vector<int> Y; rep(i,n) { Y.push_back(ys[i]); Y.push_back(ye[i]); } sort(Y.begin(),Y.end()); Y.erase(unique(Y.begin(),Y.end()),Y.end()); rep(i,n) { ys[i] = lower_bound(Y.begin(),Y.end(),ys[i]) - Y.begin(); ye[i] = lower_bound(Y.begin(),Y.end(),ye[i]) - Y.begin(); } } void compute(){ set<int> field[MAX*2]; rep(i,(int)events.size()){ Event &e = events[i]; int ID = e.ID; if( e.ID < 0 ) { // sp ( ID *= -1 ) -= 1; for(int y=ys[ID];y<=ye[ID];y++){ for(set<int>::iterator it=field[y].begin();it!=field[y].end();it++){ unit(ID,*it); } field[y].insert(ID); } } else { // ep ID -= 1; for(int y=ys[ID];y<=ye[ID];y++){ field[y].erase(ID); } } } ll maxi = 0; rep(i,n) group_area[i] = 0; rep(i,n){ group_area[find(i)] += area[i]; maxi = max(maxi,group_area[find(i)]); } cout << maxi << endl; } int main(){ while( scanf("%d",&n) != EOF ){ events.clear(); rep(i,n) { par[i] = i; int x,y,w,h; scanf("%d %d %d %d",&x,&y,&w,&h); events.push_back((Event){x,-(i+1)}); events.push_back((Event){x+w,(i+1)}); ys[i] = y; ye[i] = y + h; area[i] = (ll)w * (ll)h; } compressY(); sort(events.begin(),events.end()); compute(); } return 0; }