// @EXPECTED_RESULTS@: ACCEPTED, TIME_LIMIT_EXCEEDED // This "smart brute force" is a step in the right direction, and very close to an intended solution. // Trying more than two directions than just x and y, will most likely get AC. #pragma GCC optimize("Ofast") #include #include #include #include #include #include using namespace std; int sq(int x) { return x*x; } int main() { cin.tie(NULL)->sync_with_stdio(false); int n; cin >> n; vector> a(n); for(int j=0;j<2;++j) { for(auto& [x,y,r] : a){ if(j==0) cin >> x >> y >> r; if(j) swap(x,y); } sort(begin(a),end(a)); vector par(n); for(int i=0;i deg(n); long long iter=1.01*(long long)(n/2)*(n/2)/2+100*n+100; // for(int i=0;ix+300) break; // early break of doom --iter; if(iter<=0) { break; } if(abs(x-ox)+abs(y-oy)<=300) { // simple check to reduce heavy operations. auto D = sq(x-ox)+sq(y-oy); if(D*100<=sq(10/2*(r+oor) +2*254)) { deg[i]++; deg[j]++; // happens few times as graph is really sparse int a = find(i), b = find(j); if(a!=b) { par[a]=b; comps--; } } } } } if(iter<=0) continue; if(comps!=1 or (n>=7 and *min_element(begin(deg),end(deg))<2)) { cout << "no\n"; } else cout << "yes\n"; break; } }