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 #include #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(v) (v).begin(),(v).end() #define PII pair #define st first #define nd second #define pb push_back #define lint long long int #define VI vector #define debug(x) {cout <<#x <<" = " < v,w; vector > prefV, prefW; lint get_value(vector >& wek, lint test) { int left = 0, right = wek.size(); while (right - left > 1) { int mid = (right + left)/2; if (wek[mid].st < test) { left = mid; } else { right = mid; } } lint slope = (wek[right].nd - wek[left].nd)/(wek[right].st-wek[left].st); return wek[left].nd + (test-wek[left].st)*slope; } void dbg(vector v) { FOR(i,0,v.size()) { cerr << "(" << v[i].st <<"," << v[i].nd << ") ,"; } cerr << endl; } void dbg(vector > v) { FOR(i,0,v.size()) { cerr << "(" << v[i].st <<"," << v[i].nd << ") ,"; } cerr << endl; } void solve() { make(n); lint sum = 0; v.clear(); w.clear(); prefV.clear(); prefW.clear(); FOR(i,0,n) { make3(a, b, c); sum = sum + a * 1LL * (b-c); v.pb({b,a}); w.pb({c,a}); } if (sum != 0) { printf("NIE\n"); return; } sort(all(v)); sort(all(w)); //dbg(v); //dbg(w); prefV.pb({0,0}); prefW.pb({0,0}); vector testy; FOR(i,0,n) { prefV.pb({prefV.back().st + v[i].nd, prefV.back().nd + v[i].st * 1LL * v[i].nd}); prefW.pb({prefW.back().st + w[i].nd, prefW.back().nd + w[i].st * 1LL * w[i].nd}); testy.pb(prefV.back().st); testy.pb(prefW.back().st); } //dbg(prefV); //dbg(prefW); FOR(i,0,testy.size()) { if (get_value(prefV, testy[i]) > get_value(prefW, testy[i])) { //debug2(get_value(prefV, testy[i]), get_value(prefW, testy[i])); printf("NIE\n"); return; } } printf("TAK\n"); } int main() { make(z); while (z--) { solve(); } }