#include <iostream> #include <algorithm> #include <vector> using ll = int64_t; using point = std::pair<ll, ll>; ll dist(point const &p1, point const &p2) { return std::max(std::abs(p1.first - p2.first), std::abs(p1.second - p2.second)); } ll metric(point const &p) { return std::max(p.first, p.second); } int main() { int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<point> pxs(n); std::vector<point> pys(n); for (int i = 0; i < n; ++i) { std::cin >> pxs[i].first >> pxs[i].second; pys[i].first = pxs[i].second; pys[i].second = pxs[i].first; } std::vector<point> pts = pxs; std::vector<ll> res(n, 0); std::sort(pxs.begin(), pxs.end()); std::sort(pys.begin(), pys.end()); if (pxs[0].first != pys[0].second && pxs[0].second != pys[0].first) { std::cout << "NIE" << std::endl; continue; } auto smallest = pxs[0]; for (auto &p: pts) { p.first -= smallest.first; p.second -= smallest.second; } std::vector<int> border; std::vector<int> miss; ll height = -1, width = -1; for (int i = 0; i < n; ++i) { int c = -1, c_x = -1, c_y = -1, c_k = -1; ll dc = std::numeric_limits<ll>::max(), dc_x = std::numeric_limits<ll>::max(), dc_y = std::numeric_limits<ll>::max(), dc_k = std::numeric_limits<ll>::max(); for (int j = 0; j < n; ++j) { if (i == j) continue; if (pts[j].first < pts[i].first || pts[j].second < pts[i].second) continue; // point is in upper-right space ll d = dist(pts[i], pts[j]); if (pts[i].first == pts[j].first && d < dc_x) { dc_x = d; c_x = j; } else if (pts[i].second == pts[j].second && d < dc_y) { dc_y = d; c_y = j; } else if (pts[j].first - pts[i].first == pts[j].second - pts[i].second && d < dc_k) { dc_k = d; c_k = j; } else if (d < dc) { dc = d; c = j; } } if (c > 0 && dc < dc_x && dc < dc_y && dc < dc_k) { miss.push_back(i); continue; } if (c == -1 && c_x == -1 && c_y == -1 && c_k == -1) { border.push_back(i); continue; } res[i] = std::min({ dc_x, dc_y, dc_k }); height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } // somehow fill missed std::sort(miss.begin(), miss.end(), [&](int a, int b) { return !(metric(pts[a]) < metric(pts[b]) || pts[a] < pts[b]); }); for (auto &&i : miss) { ll b = 0; for (int j = 0; j < n; ++j) { if (i == j) continue; if (pts[j].first > pts[i].first && pts[j].second < pts[i].second && pts[j].second + res[j] > pts[i].second) { b = std::min(b, pts[j].first - pts[i].first); } if (pts[j].second > pts[i].second && pts[j].first < pts[i].first && pts[j].first + res[j] > pts[i].first) { b = std::min(b, pts[j].second - pts[i].second); } } res[i] = b; } // somehow fill borders std::sort(border.begin(), border.end(), [&](int a, int b) { return pts[a].first < pts[b].first; }); if (height > pts[border[0]].second) { // must align res[border[0]] = height - pts[border[0]].second; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].first + res[border[b - 1]] > pts[border[b]].first) { res[border[b]] = pts[border[b - 1]].second - pts[border[b]].second; } else { res[border[b]] = height - pts[border[b]].second; } } } else if (width > pts[border.back()].first) { res[border[0]] = height - pts[border[0]].first; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].second + res[border[b - 1]] > pts[border[b]].second) { res[border[b]] = pts[border[b - 1]].first - pts[border[b]].first; } else { res[border[b]] = height - pts[border[b]].first; } } } else if (height == pts[border[0]].second && width == pts[border.back()].first) { // no time, just luck for (int bb = 1; bb < border.size(); ++bb) { height = pts[border[bb - 1]].second + (pts[border[bb]].first - pts[border[bb - 1]].first); res[border[0]] = height - pts[border[0]].second; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].first + res[border[b - 1]] > pts[border[b]].first) { res[border[b]] = pts[border[b - 1]].second - pts[border[b]].second; } else { res[border[b]] = height - pts[border[b]].second; } } // final check height = width = 0; for (int i = 0; i < n; ++i) { height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } ll ds = 0; for (auto &&r : res) { ds += r * r; } if (width * height == ds) { break; } } } // final check height = width = 0; for (int i = 0; i < n; ++i) { height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } ll ds = 0; for (auto &&r: res) { ds += r * r; } if (width * height == ds) { std::cout << "TAK"; for (auto &&r: res) { std::cout << ' ' << r; } } else { std::cout << "NIE"; } std::cout << std::endl; } 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 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 | #include <iostream> #include <algorithm> #include <vector> using ll = int64_t; using point = std::pair<ll, ll>; ll dist(point const &p1, point const &p2) { return std::max(std::abs(p1.first - p2.first), std::abs(p1.second - p2.second)); } ll metric(point const &p) { return std::max(p.first, p.second); } int main() { int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<point> pxs(n); std::vector<point> pys(n); for (int i = 0; i < n; ++i) { std::cin >> pxs[i].first >> pxs[i].second; pys[i].first = pxs[i].second; pys[i].second = pxs[i].first; } std::vector<point> pts = pxs; std::vector<ll> res(n, 0); std::sort(pxs.begin(), pxs.end()); std::sort(pys.begin(), pys.end()); if (pxs[0].first != pys[0].second && pxs[0].second != pys[0].first) { std::cout << "NIE" << std::endl; continue; } auto smallest = pxs[0]; for (auto &p: pts) { p.first -= smallest.first; p.second -= smallest.second; } std::vector<int> border; std::vector<int> miss; ll height = -1, width = -1; for (int i = 0; i < n; ++i) { int c = -1, c_x = -1, c_y = -1, c_k = -1; ll dc = std::numeric_limits<ll>::max(), dc_x = std::numeric_limits<ll>::max(), dc_y = std::numeric_limits<ll>::max(), dc_k = std::numeric_limits<ll>::max(); for (int j = 0; j < n; ++j) { if (i == j) continue; if (pts[j].first < pts[i].first || pts[j].second < pts[i].second) continue; // point is in upper-right space ll d = dist(pts[i], pts[j]); if (pts[i].first == pts[j].first && d < dc_x) { dc_x = d; c_x = j; } else if (pts[i].second == pts[j].second && d < dc_y) { dc_y = d; c_y = j; } else if (pts[j].first - pts[i].first == pts[j].second - pts[i].second && d < dc_k) { dc_k = d; c_k = j; } else if (d < dc) { dc = d; c = j; } } if (c > 0 && dc < dc_x && dc < dc_y && dc < dc_k) { miss.push_back(i); continue; } if (c == -1 && c_x == -1 && c_y == -1 && c_k == -1) { border.push_back(i); continue; } res[i] = std::min({ dc_x, dc_y, dc_k }); height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } // somehow fill missed std::sort(miss.begin(), miss.end(), [&](int a, int b) { return !(metric(pts[a]) < metric(pts[b]) || pts[a] < pts[b]); }); for (auto &&i : miss) { ll b = 0; for (int j = 0; j < n; ++j) { if (i == j) continue; if (pts[j].first > pts[i].first && pts[j].second < pts[i].second && pts[j].second + res[j] > pts[i].second) { b = std::min(b, pts[j].first - pts[i].first); } if (pts[j].second > pts[i].second && pts[j].first < pts[i].first && pts[j].first + res[j] > pts[i].first) { b = std::min(b, pts[j].second - pts[i].second); } } res[i] = b; } // somehow fill borders std::sort(border.begin(), border.end(), [&](int a, int b) { return pts[a].first < pts[b].first; }); if (height > pts[border[0]].second) { // must align res[border[0]] = height - pts[border[0]].second; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].first + res[border[b - 1]] > pts[border[b]].first) { res[border[b]] = pts[border[b - 1]].second - pts[border[b]].second; } else { res[border[b]] = height - pts[border[b]].second; } } } else if (width > pts[border.back()].first) { res[border[0]] = height - pts[border[0]].first; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].second + res[border[b - 1]] > pts[border[b]].second) { res[border[b]] = pts[border[b - 1]].first - pts[border[b]].first; } else { res[border[b]] = height - pts[border[b]].first; } } } else if (height == pts[border[0]].second && width == pts[border.back()].first) { // no time, just luck for (int bb = 1; bb < border.size(); ++bb) { height = pts[border[bb - 1]].second + (pts[border[bb]].first - pts[border[bb - 1]].first); res[border[0]] = height - pts[border[0]].second; for (int b = 1; b < border.size(); ++b) { if (pts[border[b - 1]].first + res[border[b - 1]] > pts[border[b]].first) { res[border[b]] = pts[border[b - 1]].second - pts[border[b]].second; } else { res[border[b]] = height - pts[border[b]].second; } } // final check height = width = 0; for (int i = 0; i < n; ++i) { height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } ll ds = 0; for (auto &&r : res) { ds += r * r; } if (width * height == ds) { break; } } } // final check height = width = 0; for (int i = 0; i < n; ++i) { height = std::max(height, pts[i].second + res[i]); width = std::max(width, pts[i].first + res[i]); } ll ds = 0; for (auto &&r: res) { ds += r * r; } if (width * height == ds) { std::cout << "TAK"; for (auto &&r: res) { std::cout << ' ' << r; } } else { std::cout << "NIE"; } std::cout << std::endl; } return 0; } |