AOJ 0214 - Autumnal Illumination

問題文 : 秋のイルミネーション

解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.

連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.

ここで, 四角形PとQの交差判定は, Pを構成する点がQの中にあるか, または, Pの辺とQの辺が交差するか, で行った.

点が四角形に内包されているか、の判定は, 三角形に分割して行うと楽である.

コード :

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>

#define MAX_M (100)
#define EPS (1e-5)
#define SQ(X) ((X) * (X))

using namespace std;

typedef struct {
	double x, y;
} Point;

vector<Point> Rect[MAX_M];
vector<int> G[MAX_M];
bool used[MAX_M];

double getSize(double a, double b, double c)
{
	double s;
	
	s = (a + b + c) / 2.0;
	
	if (s * (s - a) * (s - b) * (s - c) <= EPS){
		return (0);
	}
	
	return (sqrt(s * (s - a) * (s - b) * (s - c)));
}

double dist(Point a, Point b)
{
	return (sqrt(SQ(a.x - b.x) + SQ(a.y - b.y)));
}

bool checkCross(vector<Point> p, vector<Point> q)
{	
	for (int i = 0; i < 4; i++){
		for (int j = i + 1; j < 4; j++){
			for (int k = j + 1; k < 4; k++){
				for (int t = 0; t < 4; t++){
					double AB = dist(p[i], p[j]), BC = dist(p[j], p[k]), CA = dist(p[k], p[i]);
					double AP = dist(p[i], q[t]), BP = dist(p[j], q[t]), CP = dist(p[k], q[t]);
					double S = getSize(AB, BC, CA);
					double M = getSize(AP, BP, AB) + getSize(AP, CP, CA) + getSize(BP, CP, BC);
					if (fabs(S - M) <= EPS){
						return (true);
					}
				}
			}
		}
	}
	
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			if (i == j) continue;
			for (int k = 0; k < 4; k++){
				for (int l = 0; l < 4; l++){
					if (k == l) continue;
					Point p1 = p[i], p2 = p[j], p3 = q[k], p4 = q[l];
					double a = (p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x);
					double b = (p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x);
					double c = (p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x);
					double d = (p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x);
					if (a * b < 0 && c * d < 0) return (true);
				}
			}
		}
	}
	
	return (false);
}

void dfs(int k)
{
	used[k] = true;
	for (int i = 0; i < (int)G[k].size(); i++){
		if (!used[G[k][i]]){
			dfs(G[k][i]);
		}
	}
}

int main()
{
	int n, m;
	int ans;
	
	while (scanf("%d", &n) && n){
		
		for (int i = 0; i < n; i++){
			scanf("%d", &m);
			for (int j = 0; j < m; j++){
				Rect[j].clear();
				G[j].clear();
			}
			
			for (int j = 0; j < m; j++){
				for (int k = 0; k < 4; k++){
					Point in;
					scanf("%lf %lf", &in.x, &in.y);
					Rect[j].push_back(in);
				}
			}
			
			for (int j = 0; j < m; j++){
				for (int k = 0; k < m; k++){
					if (checkCross(Rect[j], Rect[k]) == true){
						G[j].push_back(k);
						G[k].push_back(j);
					}
				}
			}
			
			memset(used, false, sizeof(used));
			ans = 0;
			for (int j = 0; j < m; j++){
				if (used[j] == false){
					ans++;
					dfs(j);
				}
			}
			
			printf("%d\n", ans);
		}
	}
	
	return (0);
}