#include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vvi; const ll B = 25.4*2*10; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; typedef Point P; typedef struct Quad* Q; typedef __int128_t lll; // (can be ll if coords are < 2e4) P arb(LLONG_MAX,LLONG_MAX); // not equal to any other point struct Quad { Q rot, o; P p = arb; bool mark; P& F() { return r()->p; } Q& r() { return rot->rot; } Q prev() { return rot->o->rot; } Q next() { return r()->prev(); } } *H; bool circ(P p, P a, P b, P c) { // is p in the circumcircle? lll p2 = p.dist2(), A = a.dist2()-p2, B = b.dist2()-p2, C = c.dist2()-p2; return p.cross(a,b)*C + p.cross(b,c)*A + p.cross(c,a)*B > 0; } Q makeEdge(P orig, P dest) { Q r = H ? H : new Quad{new Quad{new Quad{new Quad{0}}}}; H = r->o; r->r()->r() = r; rep(i,0,4) r = r->rot, r->p = arb, r->o = i & 1 ? r : r->r(); r->p = orig; r->F() = dest; return r; } void splice(Q a, Q b) { swap(a->o->rot->o, b->o->rot->o); swap(a->o, b->o); } Q connect(Q a, Q b) { Q q = makeEdge(a->F(), b->p); splice(q, a->next()); splice(q->r(), b); return q; } pair rec(const vector

& s) { if (sz(s) <= 3) { Q a = makeEdge(s[0], s[1]), b = makeEdge(s[1], s.back()); if (sz(s) == 2) return { a, a->r() }; splice(a->r(), b); auto side = s[0].cross(s[1], s[2]); Q c = side ? connect(b, a) : 0; return {side < 0 ? c->r() : a, side < 0 ? c : b->r() }; } #define H(e) e->F(), e->p #define valid(e) (e->F().cross(H(base)) > 0) Q A, B, ra, rb; int half = sz(s) / 2; tie(ra, A) = rec({all(s) - half}); tie(B, rb) = rec({sz(s) - half + all(s)}); while ((B->p.cross(H(A)) < 0 && (A = A->next())) || (A->p.cross(H(B)) > 0 && (B = B->r()->o))); Q base = connect(B->r(), A); if (A->p == ra->p) ra = base->r(); if (B->p == rb->p) rb = base; #define DEL(e, init, dir) Q e = init->dir; if (valid(e)) \ while (circ(e->dir->F(), H(base), e->F())) { \ Q t = e->dir; \ splice(e, e->prev()); \ splice(e->r(), e->r()->prev()); \ e->o = H; H = e; e = t; \ } for (;;) { DEL(LC, base->r(), o); DEL(RC, base, prev()); if (!valid(LC) && !valid(RC)) break; if (!valid(LC) || (valid(RC) && circ(H(RC), H(LC)))) base = connect(RC, base->r()); else base = connect(base->r(), LC->r()); } return { ra, rb }; } vector

triangulate(vector

pts) { sort(all(pts)); assert(unique(all(pts)) == pts.end()); if (sz(pts) < 2) return {}; Q e = rec(pts).first; vector q = {e}; int qi = 0; while (e->o->F().cross(e->F(), e->p) < 0) e = e->o; #define ADD { Q c = e; do { c->mark = 1; pts.push_back(c->p); \ q.push_back(c->r()); c = c->next(); } while (c != e); } ADD; pts.clear(); while (qi < sz(q)) if (!(e = q[qi++])->mark) ADD; return pts; } typedef pair pii; void NOPE(){ cout << "no\n"; exit(0); } int main(){ cin.tie(NULL),ios::sync_with_stdio(false); int n; cin >> n; vector> a(n+1); vector

pts(n+1); rep(i,0,n){ auto& [p,z] = a[i]; auto& [x,y] = p; cin >> x >> y >> z; x*=10, y*=10, z *= 5; } a[n] = {P(2e9+1,2e9),0}; sort(all(a)); rep(i,0,n+1) pts[i] = a[i].first; auto tri = triangulate(pts); vvi adj(n), dir(n); auto id = [&](P p) -> int { return lower_bound(all(pts),p)-begin(pts);}; rep(i,0,sz(tri)/3) rep(j,0,3){ int u = id(tri[i*3+j]), v = id(tri[i*3+(j+1)%3]); if ((pts[u]-pts[v]).dist2() <= (B + 1600)*(B+1600)){ adj[u].push_back(v); adj[v].push_back(u); } } for(auto& v : adj) sort(all(v)), v.erase(unique(all(v)),end(v)); vector vis(n); rep(_st,0,n){ auto [st, dst] = a[_st]; ll R = B + dst + 800, i = 0; vi q = {_st}; while(i < sz(q)){ auto at = q[i++]; ll mx = B + dst + a[at].second; if (at != _st and (pts[at]-st).dist2() <= mx*mx) dir[_st].push_back(at); for(auto to : adj[at]) if (!vis[to]) if ((st-pts[to]).dist2() <= R*R) vis[to] = 1, q.push_back(to); } for(int r : q) vis[r] = 0; } auto dfs = [&](int at, auto&& dfs) -> void { vis[at] = 1; for(auto to : dir[at]) if (!vis[to]) dfs(to,dfs);}; if (n>=7) rep(i,0,n) if (sz(dir[i]) < 2) NOPE(); dfs(0,dfs); if (count(all(vis),0)) NOPE(); cout << "yes\n"; }