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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<stdio.h>
#include<algorithm>
struct pt
{
    double a,b;
    bool operator<(const pt&x)const
    {
        if(a==x.a)
            return b<x.b;
        else
            return a<x.a;
    }
};
int main()
{
    int a,b,c,d,h,i,j,k,n,m;
    double e,f;
    scanf("%i",&n);
    for(m=0;m<n;m++)
    {

    scanf("%i",&a);
    pt * t = new pt[a];
    pt * u = new pt[a];
    for(i=0;i<a;i++)
    {
        scanf("%i %i %i",&b,&c,&d);
        e=b;
        f=c;
        t[i].a=f;
        t[i].b=e;
        f=d;
        u[i].a=f;
        u[i].b=e;
    }
    std::sort(t,t+a);
    std::sort(u,u+a);
    i=a-1;
    j=a-1;
    k=1;
    while(i>-1&&j>-1)
    {
//        printf("START\n");
        if(t[i].a==u[j].a)
        {
//            printf("ROWNE t[i].b %0.10lf u[j].b %.10lf\n",t[i].b,u[j].b);
            if((t[i].b>=u[j].b&&t[i].b-u[j].b<0.0000000001)||(t[i].b<=u[j].b&&u[j].b-t[i].b<0.0000000001))
            {
//                printf("ROWNE\n");
                t[i].b=0;
                while(t[i].b==0)
                    i--;
                u[j].b=0;
                j--;
            }
            else if(t[i].b>u[j].b)
            {
                t[i].b-=u[j].b;
                u[j].b=0;
                j--;
            }
            else if(i<=0)
            {
                k=0;
                break;
            }
            else if(t[i-1].a<u[j].a)
            {
                k=0;
                break;
            }
            else
            {
                t[i-1].b+=t[i].b;
                t[i].b=0;
                i--;
            }
//            printf("i: %i j: %i\n",i,j);
        }
        else if(t[i].a<u[j].a)
        {
            k=0;
            break;
        }
        else while(t[i].a>u[j].a)
        {
            h=i-1;
            while(t[h].b==0)
            {
                h--;
                if(h<0)
                {
                    k=0;
                    break;
                }
            }
//            printf("h: %i\n",h);
            if(h<0)
                break;
//            printf("NIEROWNE\n");
//            printf("t: %lf %lf u: %lf %lf\n",t[i].a,t[i].b,u[j].a,u[j].b);
//            printf("t[h]: %lf %lf\n",t[h].a,t[h].b);
            if(t[h].a>u[j].a)
            {
                f=(t[i].a*t[i].b+t[h].a*t[h].b)/(t[i].b+t[h].b);
                t[i].a=f;
                t[i].b+=t[h].b;
                t[h].b=0;
            }
            else
            {
                e=t[i].b*(t[i].a-u[j].a)/(u[j].a-t[h].a);
                if(e<=0)
                {
                    k=0;
                    break;
                }
//                printf("%lf\n",e);
                if(e>=t[h].b)
                {
                    f=(t[i].a*t[i].b+t[h].a*t[h].b)/(t[i].b+t[h].b);
                    t[i].a=f;
                    t[i].b+=t[h].b;
                    t[h].b=0;
                }
                else
                {
//                    printf("ROWNE PO DOLANIU\n");
                    t[i].a=u[j].a;
                    t[i].b+=e;
                    t[h].b-=e;
                }
            }
        }
        if(k==0)
            break;
    }
    if(k==0)
       printf("NIE\n");
    else printf("TAK\n");
    delete[]t;
    delete[]u;

    }
    return 0;
}