AOJ 0237 - The Last Door

問題文 : 最後の扉

解法 :
つながる三角形を列挙したら, 強連結成分分解を行うだけ. JOI のAdvertisement という問題と全く一緒になります.
問題のつながる三角形の列挙ですが, 長方形と辺が重なる or 三角形の頂点が長方形にはいる or 長方形の頂点が三角形に入る のいずれかが真ならOK です.

コード (ライブラリ略) :

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

Polygon tri[100];
int n, d;

bool isIn(Polygon a, Polygon b)
{
	for (int i = 0; i < a.size(); i++) if (isInside(b, a[i])) return (true);
	for (int i = 0; i < b.size(); i++) if (isInside(a, b[i])) return (true);
	for (int i = 0; i < a.size(); i++){
		for (int j = 0; j < b.size(); j++){
			if (isIntersect(a[i], a[(i + 1) % a.size()], b[j], b[(j + 1) % b.size()])) return (true);
		}
	}
	return (false);
}

Polygon normalize(Polygon a)
{
	if (eq(abs(a[0] - a[1]), abs(a[1] - a[2])))
		swap(a[1], a[2]);
	else if (eq(abs(a[0] - a[2]), abs(a[0] - a[1])))
		swap(a[0], a[2]);
	
	if (ccw(a[0], a[1], a[2]) != COUNTER_CLOCKWISE) swap(a[0], a[1]);
	
	return (a);
}

bool check(Polygon a, Polygon b)
{
	Polygon c;
	c.push_back(a[0]); c.push_back(a[1]);
	
	Point t = Point((a[0].x + a[1].x) / 2, (a[0].y + a[1].y) / 2);
	Point k = a[2] - t;
	c.push_back(a[1] + unitVector(k) * d); c.push_back(a[0] + unitVector(k) * d);
	
	return (isIn(c, b));
}

vector<int> G[128], rG[128];
int ord[128], gr[128];
bool vis[128];
int ctr;

void addEdge(int src, int dst)
{
	G[src].push_back(dst);
	rG[dst].push_back(src);
}

void dfs1(int v)
{
	vis[v] = true;
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]) dfs1(G[v][i]);
	}
	ord[ctr++] = v;
}

void dfs2(int v, int k)
{
	vis[v] = true;
	gr[v] = k;
	for (int i = 0; i < rG[v].size(); i++){
		if (!vis[rG[v][i]]) dfs2(rG[v][i], k);
	}
	
}

int scc()
{
	
	memset(vis, 0, sizeof(vis));
	ctr = 0;
	
	for (int i = 0; i < n; i++){
		if (!vis[i]){
			dfs1(i);
		}
	}
	
	int k = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = n - 1; i >= 0; i--){
		if (!vis[ord[i]]){
			dfs2(ord[i], k++);
		}
	}
	
	int ret = k;
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < G[i].size(); j++){
			if (gr[i] != gr[G[i][j]]){
				ret -= (1 ^ vis[gr[G[i][j]]]);
				vis[gr[G[i][j]]] = true;
			}
		}
	}
	
	return (ret);
}

int main()
{
	Point t;
	while (scanf("%d %d", &n, &d) && n + d){
		for (int i = 0; i < n; i++){
			tri[i].clear();
			for (int j = 0; j < 3; j++){
				scanf("%lf %lf", &t.x, &t.y);
				tri[i].push_back(Point(t.x, t.y));
			}
			tri[i] = normalize(tri[i]);
			G[i].clear(); rG[i].clear();
		}
		
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if (i != j && check(tri[i], tri[j])){
					addEdge(i, j);
				}	
			}
		}	
		
		printf("%d\n", scc());
	}
	
	return (0);
}