#include <cstdio> #include <cassert> #include <set> #include <algorithm> const int M = 2013; const int inf = ((int)2e9); struct point { point(long long _x, long long _y, long long _i) : x(_x), y(_y), i(_i) {} point() : x(0), y(0), i(0) {} long long x, y, i; bool operator<(const point& other) const { if (x != other.x) return x < other.x; return y < other.y; } point& operator=(const point& other) { x = other.x; y = other.y; i = other.i; return *this; } } t[M]; int n, ret[M], max_c[M]; bool go(long long min_y, long long max_y, long long w) { if (max_y <= w) return false; //printf("go %lld %lld\n",min_y, max_y); std::set<point> s; s.insert(point(t[0].x, min_y, max_y - min_y)); int next_point = 0; while (!s.empty()) { long long x = s.begin()->x; long long ya = s.begin()->y; long long yb = ya; while (!s.empty() && s.begin()->x == x && s.begin()->y == yb) { yb = s.begin()->y + s.begin()->i; s.erase(s.begin()); } if (s.empty() && next_point == n && ya == min_y && yb == max_y) return true; int i = next_point; while (i < n && t[i].x == x && t[i].y >= ya && t[i].y < yb) i++; //printf("%lld %lld %lld :: %d %d\n", x, ya, yb, next_point, i); if (i == next_point || t[next_point].y != ya) return false; long long dd = 0, dy = 0; for (int j = next_point; j < i; j++) { long long d = (j == i-1 ? yb : t[j+1].y) - t[j].y; if (d > inf || d < 1) return false; ret[t[j].i] = d; if (d != dd) { if (dd) s.insert(point(t[j-1].x + dd, dy, t[j-1].y - dy + dd)); dd = d; dy = t[j].y; } //s.insert(point(t[j].x + d, t[j].y, d)); } if (dd) s.insert(point(t[i-1].x + dd, dy, t[i-1].y - dy + dd)); next_point = i; } return false; } bool tc() { scanf("%d",&n); for (int i = 0; i < n; i++) { scanf("%lld %lld",&t[i].x, &t[i].y); t[i].i = i; } std::sort(t, t+n); long long min_y = t[0].y; long long max_y = t[0].y; for (int i = 0; i < n; i++) { min_y = std::min(min_y, t[i].y); max_y = std::max(max_y, t[i].y); } if (t[0].x == t[n-1].x || min_y == max_y) { // n identical squares. int s = n > 1 ? t[1].y-t[0].y+t[1].x-t[0].x : 1; return go(t[0].y, t[n-1].y + s, t[n-1].y); } for (int i = 0; i < n; i++) { max_c[i] = inf; for (int j = i+1; j < n; j++) { if(t[j].x >= t[i].x && t[j].y >= t[i].y) max_c[i] = std::min(max_c[i], std::max<int>(t[j].x-t[i].x, t[j].y-t[i].y)); } } int i = 0; while(i+1 < n && t[i+1].x == t[0].x) i++; long long last = 0; for (int j = i+1; j < n; j++) { long long c = t[j].x - t[i].x; // printf("%lld\n", c); if (c > last && max_c[i] >= c && t[j].y + max_c[j] >= t[i].y + c) { last = c; if (go(min_y, t[i].y+c, max_y)) { return true; } } } for (int j = 0; j < n; j++) last = std::max(last, t[j].x-t[i].x); for (int j = 0; j < n; j++) if (t[j].y < t[i].y) { long long cj = t[i].y - t[j].y; long long ci = cj + t[j].x - t[i].x; if (ci <= max_c[i] && cj <= max_c[j] && ci > last) { if (go(min_y, t[i].y + ci, max_y)) { return true; } } } return false; } int main() { int tt; scanf("%d",&tt); for (int i = 0; i < tt; i++) { if (tc()) { printf("TAK"); for (int j = 0; j < n; j++) printf(" %d", ret[j]); printf("\n"); } else puts("NIE"); } }
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 | #include <cstdio> #include <cassert> #include <set> #include <algorithm> const int M = 2013; const int inf = ((int)2e9); struct point { point(long long _x, long long _y, long long _i) : x(_x), y(_y), i(_i) {} point() : x(0), y(0), i(0) {} long long x, y, i; bool operator<(const point& other) const { if (x != other.x) return x < other.x; return y < other.y; } point& operator=(const point& other) { x = other.x; y = other.y; i = other.i; return *this; } } t[M]; int n, ret[M], max_c[M]; bool go(long long min_y, long long max_y, long long w) { if (max_y <= w) return false; //printf("go %lld %lld\n",min_y, max_y); std::set<point> s; s.insert(point(t[0].x, min_y, max_y - min_y)); int next_point = 0; while (!s.empty()) { long long x = s.begin()->x; long long ya = s.begin()->y; long long yb = ya; while (!s.empty() && s.begin()->x == x && s.begin()->y == yb) { yb = s.begin()->y + s.begin()->i; s.erase(s.begin()); } if (s.empty() && next_point == n && ya == min_y && yb == max_y) return true; int i = next_point; while (i < n && t[i].x == x && t[i].y >= ya && t[i].y < yb) i++; //printf("%lld %lld %lld :: %d %d\n", x, ya, yb, next_point, i); if (i == next_point || t[next_point].y != ya) return false; long long dd = 0, dy = 0; for (int j = next_point; j < i; j++) { long long d = (j == i-1 ? yb : t[j+1].y) - t[j].y; if (d > inf || d < 1) return false; ret[t[j].i] = d; if (d != dd) { if (dd) s.insert(point(t[j-1].x + dd, dy, t[j-1].y - dy + dd)); dd = d; dy = t[j].y; } //s.insert(point(t[j].x + d, t[j].y, d)); } if (dd) s.insert(point(t[i-1].x + dd, dy, t[i-1].y - dy + dd)); next_point = i; } return false; } bool tc() { scanf("%d",&n); for (int i = 0; i < n; i++) { scanf("%lld %lld",&t[i].x, &t[i].y); t[i].i = i; } std::sort(t, t+n); long long min_y = t[0].y; long long max_y = t[0].y; for (int i = 0; i < n; i++) { min_y = std::min(min_y, t[i].y); max_y = std::max(max_y, t[i].y); } if (t[0].x == t[n-1].x || min_y == max_y) { // n identical squares. int s = n > 1 ? t[1].y-t[0].y+t[1].x-t[0].x : 1; return go(t[0].y, t[n-1].y + s, t[n-1].y); } for (int i = 0; i < n; i++) { max_c[i] = inf; for (int j = i+1; j < n; j++) { if(t[j].x >= t[i].x && t[j].y >= t[i].y) max_c[i] = std::min(max_c[i], std::max<int>(t[j].x-t[i].x, t[j].y-t[i].y)); } } int i = 0; while(i+1 < n && t[i+1].x == t[0].x) i++; long long last = 0; for (int j = i+1; j < n; j++) { long long c = t[j].x - t[i].x; // printf("%lld\n", c); if (c > last && max_c[i] >= c && t[j].y + max_c[j] >= t[i].y + c) { last = c; if (go(min_y, t[i].y+c, max_y)) { return true; } } } for (int j = 0; j < n; j++) last = std::max(last, t[j].x-t[i].x); for (int j = 0; j < n; j++) if (t[j].y < t[i].y) { long long cj = t[i].y - t[j].y; long long ci = cj + t[j].x - t[i].x; if (ci <= max_c[i] && cj <= max_c[j] && ci > last) { if (go(min_y, t[i].y + ci, max_y)) { return true; } } } return false; } int main() { int tt; scanf("%d",&tt); for (int i = 0; i < tt; i++) { if (tc()) { printf("TAK"); for (int j = 0; j < n; j++) printf(" %d", ret[j]); printf("\n"); } else puts("NIE"); } } |