// 2009模擬地区予選 G : Neko's Treasure #include #include #include #include #include using namespace std; typedef complex P; typedef pair circle; typedef vector< vector > graph; const double EPS = 1e-8; void visit(graph &g, vector &order, vector &mark, int pos){ for(int i=0;i topologicalSort(graph &g){ vector res; vector mark(g.size(), false); for(int i=0;i EPS; } bool inCircle(circle c, P p){ return c.second-abs(c.first-p) > EPS; } bool crossCircle(circle c1, circle c2){ double r1 = c1.second; double r2 = c2.second; double d = abs(c1.first-c2.first); if(dEPS; return r1+r2-d > -EPS; } int main(){ int n; while(cin >> n, n){ double xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt; P rat = P(xs,ys), cat = P(xt,yt); vector vc; for(int i=0;i> x >> y >> r; circle c = make_pair(P(x,y),r); bool cRat = inCircle(c, rat); bool cCat = inCircle(c, cat); // ネズミか宝の一方だけを囲う壁のみが使う壁の候補になる if(cRat^cCat) vc.push_back(c); } graph g(vc.size()); // 2つの壁の順序関係を調べ,DAGを構築する // 順序関係は,宝の位置->ネズミの位置に向かったときに乗り越える順で定義。 for(int i=0;ijに枝を張る if(overlap(vc[i], vc[j])) g[i].push_back(j); } // 円iが宝を,円jがネズミを囲う if(cA==true&&cB==false){ // 円iと円jが交差しなければi->jに枝を張る if(!crossCircle(vc[i], vc[j])) g[i].push_back(j); } // 円iと円jがどちらもネズミを囲う if(cA==false&&cB==false){ // 円jが円iに完全に囲われればi->jに枝を張る if(overlap(vc[j], vc[i])) g[i].push_back(j); } } } int step[1000]; int ans = 0; memset(step, -1, sizeof(step)); // 構築したDAGをトポロジカルソート vector order = topologicalSort(g); // DAG上の最長距離ルートが答えになる for(int i=0;i