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
#include <bits/stdc++.h>

using namespace std;
#define PII pair<long double,long double>

vector<PII> A;
vector<PII> B;
queue<PII> Q1;
map<long long, long long> M;

int main()
{
    ios_base::sync_with_stdio(0);
    int q;
    cin>>q;
    while(q--)
    {
        A.clear();
        B.clear();
        while(!Q1.empty())Q1.pop();
        M.clear();
        int n;
        cin>>n;
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            long long l,a,b;
            cin>>l>>a>>b;
            sum+=l*a, sum-=l*b;
            M[a]+=l, M[b]-=l;
       //     A.push_back({a,l});
       //     B.push_back({b,l});
        }
        for(auto v:M)
        {
            long long u=v.second;
            if(u>0)A.push_back(v);
            if(u<0)B.push_back({v.first,-v.second});
        }
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());

        int ind=0;
        int czy=1;
        if(sum!=0)
        {
            cout<<"NIE"<<endl;
            continue;
        }
        for(PII &u:B)
        {
   //         cout<<" "<<A[ind].first<<" "<<u.first<<endl;
            while(A[ind].first<=u.first)
            {
                Q1.push(A[ind]);
                ind++;
                if(ind==A.size())czy=0;
            }
    //        cout<<"  ind  "<<ind<<endl;
            if(ind==A.size())czy=0;
            if(czy==0)break;
            while(true)
            {
				if(u.second<0.0000000001)break;
        //        if(!Q1.empty())cout<<Q1.front().first<<" "<<Q1.front().second;
        //        cout<<" "<<A[ind].first<<" "<<A[ind].second<<" "<<u.first<<" "<<u.second<<endl;
        //        cout<<u.first<<endl;
                if(ind==A.size())czy=0;
                if(Q1.empty())czy=0;
      //          cout<<" "<<czy<<endl;
                if(czy==0)break;
                PII x=Q1.front();
                Q1.pop();
                PII &y=A[ind];
      //          cout<<x.first<<" "<<x.second<<"  "<<u.first<<" "<<u.second<<"  "<<y.first<<" "<<y.second<<endl;
                long double kx=u.second*(y.first-u.first)/(y.first-x.first);
                long double ky=u.second*(u.first-x.first)/(y.first-x.first);
     //           cout<<"  k  "<<kx<<" "<<ky<<endl;
                if(kx<=x.second&&ky<=y.second)
                {
                    x.second-=kx, y.second-=ky;
                    Q1.push(x);
                    break;
                }
                long double sx=x.second/kx;
                long double sy=y.second/ky;
      //          cout<<"  s  "<<sx<<" "<<sy<<endl;
                if(sx<sy)
                {
                    y.second-=ky*sx;
                    u.second-=u.second*sx;
                 //   ind++;
                }
                else
                {
                    x.second-=kx*sy;
                    u.second-=u.second*sy;
                    Q1.push(x);
                    ind++;
                }
            }
            if(czy==0)break;

        }

        if(czy==0||sum!=0)cout<<"NIE"<<endl;
        else cout<<"TAK"<<endl;
    }

}