#include #include #include #include #include #include #include using namespace std; random_device rd; mt19937 rng(rd()); const double MXD = 25.4*2 + 160 + 0.00001; double sq(double x) { return x*x; } int main() { int n; cin >> n; vector> cs(n); for(auto& [x,y,r] : cs) { cin >> x >> y >> r; } int MX = n*sqrt(n); auto near = [&](int i, int j) { auto [x,y,r] = cs[i]; auto [x2,y2,r2] = cs[j]; return (sq(x-x2) + sq(y-y2) ) < sq(25.4*2 + (r+r2)/2.); }; while(true) { vector ord(n); iota(ord.begin(),ord.end(),0); vector in(n); double ang = uniform_real_distribution(0.,2*acos(-1))(rng); double sx = cos(ang),sy = sin(ang); for(int i=0;iMX) { MX*=2; continue; } vector deg(n); vector par(n); iota(begin(par),end(par),0); auto find = [&](int at) { while(at!=par[at]) { par[at] = par[par[at]]; at=par[at]; } return par[at]; }; auto addE = [&](int u, int v) { deg[u]++; deg[v]++; par[find(u)]=find(v); }; for(auto it = ord.begin();it!=ord.end();++it) { auto kt = next(it); while(kt!=ord.end() and in[*kt]-in[*it]<=MXD) { if(near(*it,*kt)) addE(*it,*kt); ++kt; } } bool good=1; if(n>=7) { if(*min_element(begin(deg),end(deg))<2) { good=0; } } for(int i=1;i