#include <bits/stdc++.h> using namespace std; #define x first #define y second const int N = 2005; int t, n, d[N], dp[N]; pair<int,int> p[N]; void solve() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second); sort(p, p+n); long long pole = 0; vector<int> zera; for (int i = 0; i < n; i++) { d[i] = 1e9; for (int j = 0; j < n; j++) if (j != i) { if (p[i].x <= p[j].x && p[i].y >= p[j].y) if (p[j].y + d[j] > p[i].y) d[i] = min(d[i], p[j].x - p[i].x); if (p[i].x >= p[j].x && p[i].y <= p[j].y) if (p[j].x + d[j] > p[i].x) d[i] = min(d[i], p[j].y - p[i].y); if (p[i].x <= p[j].x && p[i].y <= p[j].y) d[i] = min(d[i], max(p[j].x - p[i].x, p[j].y - p[i].y)); } if (d[i] == 1e9) { zera.push_back(i); d[i] = 0; } // printf("> %d - %d %d - %d\n", i, p[i].x, p[i].y, d[i]); } sort(zera.begin(), zera.end()); for (int j = 0; j < (int) zera.size(); j++) { auto z = zera[j]; // printf(">> z = %d\n", z); for (int i = 0; i < n; i++) dp[i] = d[i]; for (int i = 0; i < (int) zera.size(); i++) if (i < j) dp[zera[i]] = p[zera[i+1]].x - p[zera[i]].x; for (int i = 0; i < (int) zera.size(); i++) if (i > j) dp[zera[i]] = p[zera[i-1]].y - p[zera[i]].y; //for (int i = 0; i < n; i++) printf("%d ", dp[i]); printf("\n"); int min_x = 2e9, max_x = 0, min_y = 2e9, max_y = 0; for (int i = 0; i < n; i++) { min_x = min(min_x, p[i].x); max_x = max(max_x, p[i].x + dp[i]); min_y = min(min_y, p[i].y); max_y = max(max_y, p[i].y + dp[i]); } dp[z] = max_x - p[z].x; max_y = max(max_y, p[z].y + dp[z]); pole = 0; for (int i = 0; i < n; i++) pole += 1LL * dp[i] * dp[i]; if (pole == 1LL * (max_x - min_x) * (max_y - min_y)) { printf("TAK "); for (int i = 0; i < n; i++) printf("%d ", dp[i]); printf("\n"); return; } } puts("NIE"); } int main() { scanf("%d", &t); while (t--) solve(); return 0; }
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 | #include <bits/stdc++.h> using namespace std; #define x first #define y second const int N = 2005; int t, n, d[N], dp[N]; pair<int,int> p[N]; void solve() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second); sort(p, p+n); long long pole = 0; vector<int> zera; for (int i = 0; i < n; i++) { d[i] = 1e9; for (int j = 0; j < n; j++) if (j != i) { if (p[i].x <= p[j].x && p[i].y >= p[j].y) if (p[j].y + d[j] > p[i].y) d[i] = min(d[i], p[j].x - p[i].x); if (p[i].x >= p[j].x && p[i].y <= p[j].y) if (p[j].x + d[j] > p[i].x) d[i] = min(d[i], p[j].y - p[i].y); if (p[i].x <= p[j].x && p[i].y <= p[j].y) d[i] = min(d[i], max(p[j].x - p[i].x, p[j].y - p[i].y)); } if (d[i] == 1e9) { zera.push_back(i); d[i] = 0; } // printf("> %d - %d %d - %d\n", i, p[i].x, p[i].y, d[i]); } sort(zera.begin(), zera.end()); for (int j = 0; j < (int) zera.size(); j++) { auto z = zera[j]; // printf(">> z = %d\n", z); for (int i = 0; i < n; i++) dp[i] = d[i]; for (int i = 0; i < (int) zera.size(); i++) if (i < j) dp[zera[i]] = p[zera[i+1]].x - p[zera[i]].x; for (int i = 0; i < (int) zera.size(); i++) if (i > j) dp[zera[i]] = p[zera[i-1]].y - p[zera[i]].y; //for (int i = 0; i < n; i++) printf("%d ", dp[i]); printf("\n"); int min_x = 2e9, max_x = 0, min_y = 2e9, max_y = 0; for (int i = 0; i < n; i++) { min_x = min(min_x, p[i].x); max_x = max(max_x, p[i].x + dp[i]); min_y = min(min_y, p[i].y); max_y = max(max_y, p[i].y + dp[i]); } dp[z] = max_x - p[z].x; max_y = max(max_y, p[z].y + dp[z]); pole = 0; for (int i = 0; i < n; i++) pole += 1LL * dp[i] * dp[i]; if (pole == 1LL * (max_x - min_x) * (max_y - min_y)) { printf("TAK "); for (int i = 0; i < n; i++) printf("%d ", dp[i]); printf("\n"); return; } } puts("NIE"); } int main() { scanf("%d", &t); while (t--) solve(); return 0; } |