#include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-5; struct POINT { int x, y; POINT() : x(0), y(0) {} }; //http://dac.gijodai.ac.jp/it-con/h16_sakuhin/ippan/ippan3/math/3grade/circle/circle4.htm struct CIRCLE { POINT p; int r; bool includeStart; CIRCLE() : r(0), includeStart(false) {} CIRCLE(const POINT& p, int r, bool includeStart) : p(p), r(r), includeStart(includeStart) {} bool include(const POINT& rh) const { const int dx = p.x - rh.x; const int dy = p.y - rh.y; return dx * dx + dy * dy < r * r; } bool include(const CIRCLE& rh) const { const double h = hypot(p.x - rh.p.x, p.y - rh.p.y); return h + EPS < r - rh.r; } bool cross(const CIRCLE& rh) const { const double d = hypot(p.x - rh.p.x, p.y - rh.p.y); return abs(r - rh.r) < d + EPS && d < r + rh.r + EPS; } }; int main() { for (int n; cin >> n && n;) { POINT s, t; cin >> s.x >> s.y >> t.x >> t.y; vector circles; circles.push_back(CIRCLE(s, 0, true)); circles.push_back(CIRCLE(t, 0, false)); for (int i = 0; i < n; ++i) { CIRCLE circle; cin >> circle.p.x >> circle.p.y >> circle.r; circle.includeStart = circle.include(s); if (circle.include(s) ^ circle.include(t)) { circles.push_back(circle); } } n = circles.size(); vector > graph(n); for (int from = 0; from < n; ++from) { for (int to = 0; to < n; ++to) { if (from == to) { continue; } const CIRCLE& a = circles[from]; const CIRCLE& b = circles[to]; if (a.cross(b)) { continue; } if (a.include(b)) { if (b.includeStart) { //にぼしを囲む壁 //内側から外側に枝を張る graph[to].push_back(from); } else { //ねずみを囲む壁 //外側から内側に枝を張る graph[from].push_back(to); } } else if (!b.include(a) && !a.cross(b) && a.includeStart) { //aはにぼしを囲む壁 //bはねずみを囲む壁 //aからbに枝を張る graph[from].push_back(to); } } } for (vector >::iterator it = graph.begin(); it != graph.end(); ++it) { sort(it->begin(), it->end()); it->erase(unique(it->begin(), it->end()), it->end()); } //トポロジカルソート int memo[1024]; memset(memo, 0, sizeof(memo)); multiset > q; q.insert(make_pair(0, 0)); while (!q.empty()) { const int currentCost = q.begin()->first; const int currentNode = q.begin()->second; q.erase(q.begin()); if (memo[currentNode] > currentCost) { continue; } for (vector::iterator it = graph[currentNode].begin(); it != graph[currentNode].end(); ++it) { if (memo[*it] < currentCost + 1) { q.insert(make_pair(memo[*it] = currentCost + 1, *it)); } } } cout << memo[1] - 1 << endl; } }