Live Archive 6889 : City Park

問題リンク : https://icpcarchive.ecs.baylor.edu/external/68/6889.pdf

問題概要 :
2次元平面上に１つ以上の長方形がそれぞれオーバーラップせずに置いてある
長方形の縦と横はそれぞれy軸とx軸に平行である
２つの長方形が辺または角で接しているとき、それらの長方形は同じグループに属する
2次元平面内の存在するグループのうち、長方形の面積の総和が最大のものをみつけ、その値を出力せよ

制約 :
長方形の数は高々50000
長方形の各辺の長さは最大500

解法 :
平面走査
長方形はオーバーラップしないので2次元平面上の1点に存在しうる最大の長方形の数は高々４つ
計算量は ( 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;
}