#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <unordered_map> #include <set> using namespace std; typedef long long LL; const int INF = 1e9 + 7; vector<pair<int, int>> v; bool ok, byl; vector<vector<int>> pre; int mnl = INF, mnd = INF, mxg, mxp, zp, zg; int n; set<pair<int, int>> st; void read() { cin >> n; mnl = INF, mnd = INF, mxg = 0, mxp = 0; v.clear(); st.clear(); for(int i = 0; i < n; i++) { int x, y; cin >> x >> y; x++, y++; v.push_back({x, y}); mnl = min(mnl, x); mnd = min(mnd, y); mxp = max(mxp, x); mxg = max(mxg, y); } for(auto vv: v) if(vv.first == mnl && vv.second == mnd) ok = 1; mxg -= (mnd - 1); mxp -= (mnl - 1); } bool check(int x, int y, int r) { //cout << x << " " << y << " " << r << endl; if(x + r > zp || y + r > zg) { return 0; } for(int i = y; i < y + r; i++) { for(int j = x; j < x + r; j++) { if(i == y && j == x) continue; if(st.find({j, i}) != st.end()) { return 0; } } } return 1; } int Find1(int x, int y) { int r = 1; while(check(x, y, r)) r++; return (r - 1) * (r - 1); } int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //cout.tie(0); int t; cin >> t; while(t--) { ok = 0; read(); if(!ok) { cout << "NIE" << "\n"; continue; } for(int i = 0; i < (int)v.size(); i++) { v[i].first -= (mnl - 1); v[i].second -= (mnd - 1); st.insert({v[i].first, v[i].second}); } vector<int> res; res.resize(n + 10, 0); int cnt = 0; byl = 0; for(int i = mxg + 1; i <= 1000; i++) { for(int j = mxp + 1; j <= 1000; j++) { //cout << "aaa " << i << " " << j << endl; zg = i, zp = j; cnt = 0; for(int k = 0; k < (int)v.size(); k++) { int ans = Find1(v[k].first, v[k].second); res[k + 1] = ans; cnt += ans; } if(cnt == (i - 1) * (j - 1)) { cout << "TAK "; for(int l = 1; l <= n; l++) cout << sqrt(res[l]) << " "; cout << "\n"; byl = 1; break; } } if(byl) break; } if(!byl) cout << "NIE\n"; } 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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <unordered_map> #include <set> using namespace std; typedef long long LL; const int INF = 1e9 + 7; vector<pair<int, int>> v; bool ok, byl; vector<vector<int>> pre; int mnl = INF, mnd = INF, mxg, mxp, zp, zg; int n; set<pair<int, int>> st; void read() { cin >> n; mnl = INF, mnd = INF, mxg = 0, mxp = 0; v.clear(); st.clear(); for(int i = 0; i < n; i++) { int x, y; cin >> x >> y; x++, y++; v.push_back({x, y}); mnl = min(mnl, x); mnd = min(mnd, y); mxp = max(mxp, x); mxg = max(mxg, y); } for(auto vv: v) if(vv.first == mnl && vv.second == mnd) ok = 1; mxg -= (mnd - 1); mxp -= (mnl - 1); } bool check(int x, int y, int r) { //cout << x << " " << y << " " << r << endl; if(x + r > zp || y + r > zg) { return 0; } for(int i = y; i < y + r; i++) { for(int j = x; j < x + r; j++) { if(i == y && j == x) continue; if(st.find({j, i}) != st.end()) { return 0; } } } return 1; } int Find1(int x, int y) { int r = 1; while(check(x, y, r)) r++; return (r - 1) * (r - 1); } int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //cout.tie(0); int t; cin >> t; while(t--) { ok = 0; read(); if(!ok) { cout << "NIE" << "\n"; continue; } for(int i = 0; i < (int)v.size(); i++) { v[i].first -= (mnl - 1); v[i].second -= (mnd - 1); st.insert({v[i].first, v[i].second}); } vector<int> res; res.resize(n + 10, 0); int cnt = 0; byl = 0; for(int i = mxg + 1; i <= 1000; i++) { for(int j = mxp + 1; j <= 1000; j++) { //cout << "aaa " << i << " " << j << endl; zg = i, zp = j; cnt = 0; for(int k = 0; k < (int)v.size(); k++) { int ans = Find1(v[k].first, v[k].second); res[k + 1] = ans; cnt += ans; } if(cnt == (i - 1) * (j - 1)) { cout << "TAK "; for(int l = 1; l <= n; l++) cout << sqrt(res[l]) << " "; cout << "\n"; byl = 1; break; } } if(byl) break; } if(!byl) cout << "NIE\n"; } return 0; } |