AOJ : 0214 - 秋のイルミネーション (Autumnal Illumination)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0214&lang=jp
日本語の問題文なので, 説明省略

アルゴリズム

最低条件 : 四角形と四角形の交差判定が完成していること
これさえできていれば, どの四角形とどの四角形が交差しているかの判定 (グループ分け) を行うだけです.
これをするためには, Union-Find木を使いましょう.

プログラム

コードを大幅省略しています.

int main(void){
  int n;

  while(cin>>n,n) while(n--) {
    int m; cin>>m;
    vector<P> pol[m];
    init(m); //Union-Find木初期化

    rep(i,m){
      //四角形取得
      rep(j,4){
        P p; cin>>p.real()>>p.imag();
        pol[i].push_back(p);
      }
      //現在取得した四角形が, 今まで出てきた四角形と重なるか判定 -> 
      rep(j,i) if(intersect_pol_pol(pol[i],pol[j])) {
        //もし重なってたら, Union-Find木のiとjを併合
        unite(i,j);
      }
    }

    //Union-Find木の, 各要素の根をsetに突っ込んでいけば,
    //最終的にいくつのグループがあるかわかる
    set<int> ans;
    rep(i,m) ans.insert(find(i));
    cout<<ans.size()<<endl;
  }

  return 0;
}