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; }