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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 //Author: Piotr Zielinski #include using namespace std; typedef long long LL; typedef pair PII; const int N = 2e3+5; long double EPS = 0.0000001; void solve() { int n, l, a, b; LL sumSrc = 0, sumDest = 0; cin >> n; vector src(n); vector dest(n); queue Q; for(int i = 0;i < n;++i) { cin >> l >> a >> b; src[i] = {a, l}; dest[i] = {b, l}; sumSrc += 1LL*l*a; sumDest += 1LL*l*b; } if(sumSrc != sumDest) { cout << "NIE\n"; return; } sort(src.begin(), src.end()); sort(dest.begin(), dest.end()); if(src[0].first > dest[0].first || src.back().first < dest.back().first) { cout << "NIE\n"; return; } int destCt = 0; a = 0, b = 0; while(b < n && destCt < n) { if(src[b].second <= EPS) { ++b; continue; } if(dest[destCt].first == src[b].first) { if(src[b].second < dest[destCt].second) { dest[destCt].second -= src[b].second; src[b].second = 0.0; ++b; continue; } src[b].second -= dest[destCt].second; ++destCt; continue; } if(dest[destCt].first+EPS >=src[b].first) { Q.push(src[b]); ++b; continue; } if(Q.empty()) { cout << "NIE\n"; return; } PII past = Q.front(); Q.pop(); long double x = (dest[destCt].second * (dest[destCt].first-src[b].first)) / (past.first - src[b].first); long double y = (dest[destCt].second * (past.first-dest[destCt].first)) / (past.first - src[b].first); if(past.second+EPS >= x && src[b].second+EPS >= y) { past.second -= x; src[b].second -= y; ++destCt; if(past.second > EPS) Q.push(past); //cout << "1 case" << endl; continue; } else if((past.second*(dest[destCt].first-past.first)) / (src[b].first-dest[destCt].first) <= src[b].second+EPS) { src[b].second -= (past.second*(dest[destCt].first-past.first)) / (src[b].first-dest[destCt].first); dest[destCt].second -= (past.second*(src[b].first-past.first)) / (src[b].first-dest[destCt].first); //cout << "2 case" << endl; continue; //cout << "AAAA " << x << " " << y << " " << src[a+2].second << " " << (x*(dest[destCt].first-src[a+1].first)) / (src[b].first-dest[destCt].first) << endl; } else { past.second -= (src[b].second*(dest[destCt].first-src[b].first)) / (past.first-dest[destCt].first); dest[destCt].second -= (src[b].second*(past.first-src[b].first)) / (past.first-dest[destCt].first); if(past.second > EPS) Q.push(past); ++b; //cout << "3 case" << endl; continue; } } //cout << a << " " << b <<" " << destCt << endl; if(destCt < n && dest[destCt].second > EPS) { cout << "NIE\n"; return; } cout << "TAK\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T --> 0) solve(); return 0; }