AOJ0214 秋のイルミネーション

解法

---

四角形の交差判定が出来れば勝ち。
あとはUnionFind使っただけ。

四角形の交差判定は、
1.aがbの中にある
2.bがaの中にある
3.aの各辺がbの各辺でどれか交差する
こんな感じでやった。

ライブラリ作ったのでやってみたけど、ライブラリあるといい(小並感)

ソース

---

#include<iostream>
#include<complex>
#include<vector>
using namespace std;
typedef complex < double > P;
typedef vector< P > G;
vector< G > g;
const double EPS = 1e-8;
const double INF = 1e12;
double cross(const P& a,const P& b){ //外積
  return imag(conj(a) * b);
}
double dot(const P& a,const P& b){ // 内積
  return real(conj(a) * b);
}
struct L: vector < P >{
  L(const P& a,const P& b){
    push_back(a);
    push_back(b);
  }
};
int ccw(P a,P b,P c){
  b -= a; c -= a;
  if(cross(b,c) > 0) return 1;
  if(cross(b,c) < 0) return -1;
  if(dot(b,c) < 0) return 2; // c--a--b
  if(norm(b) < norm(c)) return -2; // a--b--c
  return 0; // a--c--b
}
bool intersectSS(const L& s,const L& t){ //交差判定 線分:線分
  return ccw(s[0],s[1],t[0]) * ccw(s[0],s[1],t[1]) <= 0 &&
    ccw(t[0],t[1],s[0]) * ccw(t[0],t[1],s[1]) <= 0;
}
#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]
bool conteins(const G& Q, const P& p){
  bool in = false;
  for(int i = 0 ; i < Q.size() ; i++ ){
    P a = curr(Q,i) - p, b = next(Q,i) - p;
    if(imag(a) > imag(b)) swap(a,b);
    if(imag(a) <= 0 && 0 < imag(b) && cross(a,b) < 0) in = !in;
    if(cross(a,b) == 0 && dot(a,b) <= 0) return true;
  }
  return in;
}
bool intersect( int x, int y){ //交差判定 g[x] == g[y]
  // g[x] or g[y] が包容
  for(int i = 0 ; i < 4 ; i++ ){
    if(conteins(g[y],g[x][i]) || conteins(g[x],g[y][i])) return true;
  }
  // g[x] と g[y]の辺が交差
  for(int i = 0 ; i < 4 ; i++ ){
    for(int j = 0 ; j < 4 ; j++ ){
      if(intersectSS(L(curr(g[x],i),next(g[x],i)),L(curr(g[y],j),next(g[y],j)))) return true;
    }
  }
  return false;
}
//UnionFind
vector< int > rank, p;
void link(int x,int y){
  if(rank[x] > rank[y]) p[y] = x;
  else{
    p[x] = y;
    if(rank[x] == rank[y]) rank[y]++;
  }
}
void init(int size){
  rank.resize(size);
  p.resize(size);
  for(int i = 0 ; i < size ; i++ ){
    p[i] = i, rank[i] = 0;
  }
}
int findSet(int x){
  if(x != p[x]) p[x] = findSet(p[x]);
  return p[x];
}
void Union(int x,int y){
  link(findSet(x),findSet(y));
}
bool isSame(int x,int y){
  return findSet(x) == findSet(y);
}

int main(){
  int N, M;
  while(cin >> N , N){
    for(int i = 0 ; i < N ; i++ ){
      cin >> M;
      g.resize(M);
      init(M);
      for(int j = 0 ; j < M ; j++ ){
        for(int k = 0 ; k < 4 ; k++ ){
          P buff;
          cin >> buff.real() >> buff.imag();
          g[j].push_back(buff);
        }
      }
      for(int j = 0 ; j < M ; j++ ){
        for(int k = 0 ; k < j ; k++ ){
          if(!isSame( j, k) && intersect( j, k)) Union( j, k);
        }
      }
      int ret = 0;
      for(int j = 0 ; j < M ; j++ ){
        if(findSet(j) == j) ret++;
      }
      cout << ret << endl;
      g.clear();
    }
  }
}