AOJ 0237 The Last Door

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0237）

二等辺三角形が座標平面上にn個ある。
触れると、底辺から、長さdの光の長方形が出る。
光の長方形に触れた（共有点をもった）別の三角形は、連鎖的に同様に光る。

すべての三角形を光らせるのに必要な、触れるべき三角形の個数の最小値を求めよ。

制約条件

n, dは整数
n≦100
座標は実数
線分から距離0.01以内にある点は、線分上にあるとみなす。

方針

グラフを作って強連結成分分解するとDAGになるので、入次数0の頂点を数えるだけ。
こないだのatcoderのDと同じ。

超やるだけなんだけど、問題文が曖昧すぎかつ、eps = 0.01の超クソゲー。
30回くらいWA出した。

ソースコード

int n, d;
vector<vi> g;

int main(){
	while(cin >> n >> d, n || d){
		g.clear(); g.resize(n);
		vector<G> tri;
		rep(i, n){
			int t = -1;
			G p(3);
			double l[3];
			rep(j, 3) cin >> p[j].real() >> p[j].imag();
			rep(j, 3) l[j] = abs(p[j] - p[(j + 1) % 3]);
			rep(j, 3) if(abs(l[j] - l[(j + 1) % 3]) < EPS){
				t = (j + 1) % 3;
				break;
			}
			assert(t >= 0);
			if(t) swap(p[t], p[0]);
			tri.pb(p);
		}
		
		rep(i, n){
			G &p = tri[i];
			P dir = p[0] - (p[1] + p[2]) * 0.5;
			dir *= d / abs(dir);
			
			G ps;
			ps.pb(p[1]); ps.pb(p[2]);
			ps.pb(p[1] + dir); ps.pb(p[2] + dir);
			ps = convex_hull(ps);
			
			rep(j, n){
				bool ok = 0;
				rep(k, 3){
					rep(l, 4) if(distanceSP(L(ps[l], ps[(l + 1) % 4]), tri[j][k])
						< 0.01) ok = 1;
					if(contains(ps, tri[j][k]) != OUT) ok = 1;
				}
				if(ok) g[i].pb(j);
			}
		}
		
		int ans = 0;
		map<int, int> to;
		vector<vi> scc;
		stronglyConnectedComponents(g, scc);
		int m = scc.size();
		vi in(m);
		
		rep(i, m) rep(j, scc[i].size()){
			to[scc[i][j]] = i;
		}
		rep(i, n) rep(j, g[i].size()){
			int a = to[i], b = to[g[i][j]];
			if(a != b) in[b]++;
		}
		rep(i, m) if(in[i] == 0) ans++;
		cout << ans << endl;
	}
	return 0;
}