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
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <time.h>

#ifdef TS_TEST
#define TS_TIMER_START(t) do { (t) = clock(); } while (0)
#define TS_TIMER_SHOW(t, title) do {\
        int msec = (clock() - (t)) * 1000 / CLOCKS_PER_SEC;\
        fprintf(stderr, "%s: %d.%03d\n", (title), msec/1000, msec%1000);\
    } while (0)
#else
#define TS_TIMER_START(t)
#define TS_TIMER_SHOW(t, title)
#endif

#define MIN(a, b) ((a) <= (b) ? (a) : (b))
#define MAX(a, b) ((a) >= (b) ? (a) : (b)) 

#define N_MAX 50000

typedef long long i64;

struct car {
    int h;
    int x_poc;
    int x_kon;
};

int n;
int w;
struct car c[N_MAX] = { 0 };
int a[N_MAX] = { 0 };

void
load_data()
{
    int i;
    int x1, y1, x2, y2;
    scanf("%d %d", &n, &w);
    for (i = 0;  i < n;  i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        c[i].h = (y2 > y1) ? y2 - y1 : y1 - y2;
        c[i].x_poc = MIN(x1, x2);
    }
    for (i = 0;  i < n;  i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        c[i].x_kon = MIN(x1, x2);
    }
}

int
compare_x_poc(const struct car *p1, const struct car *p2)
{
    return p2->x_poc - p1->x_poc;
}

int
compare_x_kon(const int *p1, const int *p2)
{
    return c[*p2].x_kon - c[*p1].x_kon;
}

void
init_data()
{
    int i;
    for (i = 0; i < n; i++) {
        a[i] = i;
    }
    qsort(&c[0], n, sizeof(c[0]), compare_x_poc);
    qsort(&a[0], n, sizeof(a[0]), compare_x_kon);
}

int
is_blocked(int j)
{
    int g, k;
    g = w - c[j].h;
    for (k = j - 1; k >= 0; k--) {
        if (c[k].h > g) {
            return 1;
        }
    }
    return 0;
}

void
remove_car(int j)
{
    c[j].h = 0;
}

void
compute()
{
    int i, j;
    for (i = 0; i < n - 1; i++) {
        j = a[i];
        if (is_blocked(j)) {
            puts("NIE");
            return;
        }
        remove_car(j);
    }
    puts("TAK");
}

int
main()
{
    int t;
    int i;
    clock_t cl_total;
    TS_TIMER_START(cl_total);
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        load_data();
        init_data();
        compute();
    }
    TS_TIMER_SHOW(cl_total, "Total time");
    return 0;
}