1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include #define fi first #define sc second #define mp make_pair #define pb push_back #define forn(I,P,K) for(int (I)=(P);(I)<=(K);++(I)) using namespace std; typedef long long ll; typedef long double ld; typedef pair para; const ld eps=0.0000001; vector A,B; queue Q; inline int solve() { A.clear(); B.clear(); while(!Q.empty()) Q.pop(); int n; ll ax=0,bx=0; cin>>n; forn(i,1,n) { int l,a,b; cin>>l>>a>>b; A.pb({a,l}); B.pb({b,l}); ax+=1LL*a*l; bx+=1LL*b*l; } if(ax!=bx) return cout<<"NIE\n",0; sort(A.begin(),A.end()); sort(B.begin(),B.end()); int ind=0; for(auto &v:B) { while(ind<(int)A.size()&&A[ind].fi<=v.fi+eps) { Q.push(A[ind]); ind++; } while(v.sc>eps) { if(Q.empty()) return cout<<"NIE\n",0; auto x=Q.front(); Q.pop(); para y; if(ind>=(int)A.size()) y=mp(0,0); else y=A[ind]; ld alfa=v.sc*(v.fi-y.fi)/(x.fi-y.fi); ld beta=v.sc*(x.fi-v.fi)/(x.fi-y.fi); if(alfa<=x.sc+eps&&beta<=y.sc+eps) { x.sc-=alfa; y.sc-=beta; if(x.sc>eps) Q.push(x); if(y.sc>eps) { if(ind<(int)A.size()) A[ind]=y; } else ind++; break; } else if(x.sc*(v.fi-x.fi)/(y.fi-v.fi)<=y.sc+eps) { y.sc-=x.sc*(v.fi-x.fi)/(y.fi-v.fi); v.sc-=x.sc*(y.fi-x.fi)/(y.fi-v.fi); if(y.sc>eps) { if(ind<(int)A.size()) A[ind]=y; } else ind++; } else { x.sc-=y.sc*(v.fi-y.fi)/(x.fi-v.fi); v.sc-=y.sc*(x.fi-y.fi)/(x.fi-v.fi); if(x.sc>eps) Q.push(x); ind++; } } } return cout<<"TAK\n",0; } int main() { ios_base::sync_with_stdio(0); int Z; cin>>Z; while(Z--) solve(); return 0; }