解法
四角形の交差判定が出来れば勝ち。
あとは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();
}
}
}
