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 #include #define x first #define y second using namespace std; using L = long long; using D = long double; const D EPS = 1e-6; pair kub_st[100100], kub_en[100100]; int n, t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> t; while(t--) { L checkSum1 = 0, checkSum2 = 0; cin >> n; for(int i = 0; i < n; ++i) { L l, a, b; cin >> l >> a >> b; checkSum1 += l * a; checkSum2 += l * b; kub_st[i] = {a, l}; kub_en[i] = {b, l}; } if(checkSum1 != checkSum2) { cout << "NIE\n"; continue; } sort(kub_st, kub_st + n, greater>()); sort(kub_en, kub_en + n, greater>()); /*for(int i = 0; i < n; ++i) { cout << kub_st[i].x << ' ' << kub_st[i].y << ' ' << kub_en[i].x << ' ' << kub_en[i].y << '\n'; }*/ int pgt = 0, plt = 0; bool doable = true; //int kebab = 0; for(int i = 0; i < n; ++i) { //cout << i << " :HMM\n"; while(doable) { //if(++kebab > 10) return 0; //cout << pgt << ' ' << plt << ' ' << kub_st[pgt].x << ' ' << kub_st[pgt].y << ' ' << kub_st[plt].x << ' ' << kub_st[plt].y << ' ' << kub_en[i].x << ' ' << kub_en[i].y << '\n'; if(kub_st[pgt].x == kub_en[i].x) { D g = min(kub_st[pgt].y, kub_en[i].y); kub_st[pgt].y -= g; kub_en[i].y -= g; } if(abs(kub_en[i].y) < EPS) break; if(abs(kub_st[pgt].y) < EPS) { ++pgt; if(pgt == n) doable = false; if(abs(kub_en[i].y) > EPS && kub_en[i].x > kub_st[pgt].x) doable = false; continue; } if(kub_st[pgt].x < kub_en[i].x) { doable = false; break; } while((kub_st[plt].x >= kub_en[i].x || abs(kub_st[plt].y) < EPS) && plt < n) { ++plt; } if(plt == n) { doable = false; break; } //cout << (kub_en[i].x - kub_st[plt].x) << ' ' << (kub_st[pgt].x - kub_st[plt].x) << '\n'; D percent = (kub_en[i].x - kub_st[plt].x) / (kub_st[pgt].x - kub_st[plt].x); D fA = kub_st[pgt].y / percent; D fB = kub_st[plt].y / (1.0 - percent); D fMin = min({fA, fB, kub_en[i].y}); kub_st[pgt].y -= fMin * percent; kub_st[plt].y -= fMin * (1.0 - percent); kub_en[i].y -= fMin; } if(!doable) break; } if(doable) cout << "TAK\n"; else cout << "NIE\n"; //cout << "NIEWIEM!\n"; } return 0; }