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; }