#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Point { long long x, y, a; int id; Point() {} Point(long long _x, long long _y, int _id) : x(_x), y(_y), id(_id) {} }; bool cmp(Point a, Point b) { return (a.y == b.y) ? a.x < b.x : a.y < b.y; } vector <Point> data; vector <Point> vec; long long a1, a2, b1, b2; int n, t; bool prog() { a2 = b2 = 0; a1 = vec[0].x; b1 = vec[0].y; int i, j; long long k, x, y, x1, y1, a; for(i = 0; i < vec.size(); ++i) { x = vec[i].x; y = vec[i].y; j = i + 1; while(vec[j].y == y && j < n) ++j; if(j == n) y1 = -1; else y1 = vec[j].y; x1 = 2000000009; for(j = 0; j < data.size(); ++j) if(data[j].id != vec[i].id && data[j].x > x && data[j].y >= y && data[j].x < x1) x1 = data[j].x; if(x1 == 2000000009) x1 = -1; if(x1 - vec[i].x != y1 - vec[i].y && x1 != -1 && y1 != -1) return false; else if(x1 == -1 && y1 == -1) { a = a2 - x; } else if( x1 == -1) a = y1 - y; else if( y1 == -1) a = x1 - x; else a = x1 - x; vec[i].a = a; if(a2 < x + a) a2 = x + a; if(b2 < y + a) b2 = y + a; } for(i = 0; i < n; ++i) data[vec[i].id - 1].a = vec[i].a; unsigned long area1, area2; area1= (a2 - a1) * (b2 - b1); area2= 0; for(i = 0; i < n; ++i) area2 += (data[i].a * data[i].a); return area1 == area2; } int main() { int i, j; long long x , y; cin >> t; while(t--) { cin >> n; for(i = 1; i <= n; ++i) { cin >> x >> y; data.push_back(Point(x, y, i)); vec.push_back(Point(x, y, i)); } sort(vec.begin(), vec.end(), cmp); if(prog()) { cout << "TAK "; for(i = 0; i < n; ++i) cout << data[i].a << ' '; cout << '\n'; } else cout << "NIE\n"; data.clear(); vec.clear(); } 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 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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Point { long long x, y, a; int id; Point() {} Point(long long _x, long long _y, int _id) : x(_x), y(_y), id(_id) {} }; bool cmp(Point a, Point b) { return (a.y == b.y) ? a.x < b.x : a.y < b.y; } vector <Point> data; vector <Point> vec; long long a1, a2, b1, b2; int n, t; bool prog() { a2 = b2 = 0; a1 = vec[0].x; b1 = vec[0].y; int i, j; long long k, x, y, x1, y1, a; for(i = 0; i < vec.size(); ++i) { x = vec[i].x; y = vec[i].y; j = i + 1; while(vec[j].y == y && j < n) ++j; if(j == n) y1 = -1; else y1 = vec[j].y; x1 = 2000000009; for(j = 0; j < data.size(); ++j) if(data[j].id != vec[i].id && data[j].x > x && data[j].y >= y && data[j].x < x1) x1 = data[j].x; if(x1 == 2000000009) x1 = -1; if(x1 - vec[i].x != y1 - vec[i].y && x1 != -1 && y1 != -1) return false; else if(x1 == -1 && y1 == -1) { a = a2 - x; } else if( x1 == -1) a = y1 - y; else if( y1 == -1) a = x1 - x; else a = x1 - x; vec[i].a = a; if(a2 < x + a) a2 = x + a; if(b2 < y + a) b2 = y + a; } for(i = 0; i < n; ++i) data[vec[i].id - 1].a = vec[i].a; unsigned long area1, area2; area1= (a2 - a1) * (b2 - b1); area2= 0; for(i = 0; i < n; ++i) area2 += (data[i].a * data[i].a); return area1 == area2; } int main() { int i, j; long long x , y; cin >> t; while(t--) { cin >> n; for(i = 1; i <= n; ++i) { cin >> x >> y; data.push_back(Point(x, y, i)); vec.push_back(Point(x, y, i)); } sort(vec.begin(), vec.end(), cmp); if(prog()) { cout << "TAK "; for(i = 0; i < n; ++i) cout << data[i].a << ' '; cout << '\n'; } else cout << "NIE\n"; data.clear(); vec.clear(); } return 0; } |