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 #include using namespace std; const int INF = 2e9; struct punkt { int x; int y; int bok; }; void solve() { int n; scanf("%d", &n); if(n==1){ printf("TAK 1\n"); return;} pair p[n]; int odp[n]; int lewy = INF, maksprawy = -1; int dolny = INF, maksgorny = -1; for(int i = 0; i < n; i++) { scanf("%d%d", &p[i].second, &p[i].first); lewy = min(lewy, p[i].second); dolny = min(dolny, p[i].first); maksprawy = max(maksprawy, p[i].second); maksgorny = max(maksgorny, p[i].first); odp[i] = 0; } vector naKoniec; for(int i = 0; i < n; i++) { int minOdl = INF; for(int j = 0; j < n; j++) { if(i==j) continue; int x1 = p[i].second, y1 = p[i].first; int x2 = p[j].second, y2 = p[j].first; if(x2>x1 and y2>y1) minOdl = min(max(x2-x1, y2-y1), minOdl); else if(x2==x1 and y2>y1) minOdl = min(minOdl, y2-y1); else if(x2>x1 and y2==y1) minOdl = min(minOdl, x2-x1); } if(minOdl==INF) naKoniec.push_back(-i); else { odp[i] = minOdl; maksprawy = max(maksprawy, p[i].second+minOdl); maksgorny = max(maksgorny, p[i].first+minOdl); } } sort(naKoniec.begin(), naKoniec.end()); for(int i = 0; i < naKoniec.size(); i++) naKoniec[i] = abs(naKoniec[i]); for(int i = 0; i < naKoniec.size(); i++) { int i1 = naKoniec[i]; int o1 = min(maksprawy-p[i1].second, maksgorny-p[i1].first); if(o1==0) o1 = max(maksprawy-p[i1].second, maksgorny-p[i1].first); odp[i1] = o1; maksprawy = max(maksprawy, o1+p[i1].second); maksgorny = max(maksgorny, o1+p[i1].first); } int A = maksprawy-lewy, B = maksgorny-dolny; int pole = A*B; for(int i = 0; i < n; i++) { pole -= odp[i]*odp[i]; } if(pole==0) { printf("TAK "); for(int i = 0; i < n; i++) { printf("%d ", odp[i]); } printf("\n"); } else printf("NIE\n"); } int main() { int t; scanf("%d", &t); while(t--) solve(); }