ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0214 Autumnal Illumination

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0214

いろんな四角形がくっついているかどうかを判定したりする問題です。


・解法
Union-Find木 + 幾何的な処理(点と多角形の内包関係、線分と線分の交差判定) で解くことができます。

ライブラリ等を持っていればわりとあっさりできてしまうのではないでしょうか。


ソースコード
※ライブラリ等は省略

#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;

static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
typedef complex<double> Point; 
typedef vector<Point> Polygon;


int par[100];  //親
int rank[100]; //木の深さ

int N,M;
Polygon polygon[100];

int main(){
   while(cin >> N){
      if(N==0)break;

      while(N--){
         cin >> M;
         init(M);
	 
         for(int i = 0 ; i < M ; i++){
            polygon[i].clear();
         }
	 
         for(int i = 0 ; i < M ; i++){
            for(int j = 0 ; j < 4 ; j++){
               int x,y;
               cin >> x >> y;
               polygon[i].push_back(Point(x,y));
            }
         }

         for(int i = 0 ; i < M ; i++){
            for(int j = 0 ; j < M ; j++){
               if(i==j)continue;
               
               for(int k = 0 ; k < 4 ; k++){
                  if(contains(polygon[i], polygon[j][k])!=OUT){
                     unite(i,j);
                     break;
                  }
		  
                  if(intersectPS(polygon[i], polygon[j][k], polygon[j][(k+1)%4])){
                     unite(i,j);
                     break;
                  }
		 
               }
            }
         }
        
         set<int>ans;
         for(int i = 0 ; i < M ; i++){
            ans.insert(find(i));
         }
         cout << ans.size() << endl;
      }
   }
   return 0;
}