#include <iostream> #include <algorithm> #include <vector> using namespace std; void sortuj(vector<vector<unsigned long long>> &matrix, int kolumna) { sort(matrix.begin(), matrix.end(), [kolumna](const vector<unsigned long long> &lhs, const vector<unsigned long long> &rhs) { return lhs[kolumna] < rhs[kolumna]; }); } int main() { int liczbaTestow; cin >> liczbaTestow; while (liczbaTestow--) { int liczbaPunktow; cin >> liczbaPunktow; vector<vector<unsigned long long>> tab; unsigned long long x; unsigned long long y; unsigned long long indeks = 0; for (int i = 0; i < liczbaPunktow; i++) { cin >> x; cin >> y; vector<unsigned long long> pom; pom.push_back(x); pom.push_back(y); pom.push_back(indeks++); tab.push_back(pom); } sortuj(tab, 0); unsigned long long maxY,minY,minX,maxX; minX = maxX = tab[0][0]; minY = maxY = tab[0][1]; bool ostY = false; bool pokaz = false; for (int i = 1; i < liczbaPunktow; i++) { if (minY > tab[i][1]) { cout << "NIE"<<endl; pokaz = true; break; } if (tab[i][1] > tab[i - 1][1]) { ostY = true; tab[i - 1][2] = tab[i][1] - tab[i - 1][1]; } else { if (ostY) { //TODO: Zrobić co się stanie jak było potem X tab[i-1][2]=tab[i-1][1]-tab[i][1]; } } if (!ostY) { tab[i - 1][2] = tab[i][0] - tab[i - 1][0]; } if (maxY <= tab[i][1] + tab[i][2]) maxY = tab[i][1] + tab[i][2]; if (maxX <= tab[i][0] + tab[i][2]) maxX = tab[i][0] + tab[i][2]; } tab[liczbaPunktow - 1][2] = maxY - tab[liczbaPunktow - 1][1]; unsigned long long pole = (maxY - minY) * (maxX - minX); unsigned long long polezdanych = 0; for (int i = 0; i < liczbaPunktow; i++) polezdanych += tab[i][2] * tab[i][2]; if (pokaz); else if (polezdanych == pole) { cout << "TAK "; for (int i = 0; i < liczbaPunktow; i++) cout << tab[i][2] << " "; cout<<endl; } else if (polezdanych != pole) cout << "NIE"<<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 | #include <iostream> #include <algorithm> #include <vector> using namespace std; void sortuj(vector<vector<unsigned long long>> &matrix, int kolumna) { sort(matrix.begin(), matrix.end(), [kolumna](const vector<unsigned long long> &lhs, const vector<unsigned long long> &rhs) { return lhs[kolumna] < rhs[kolumna]; }); } int main() { int liczbaTestow; cin >> liczbaTestow; while (liczbaTestow--) { int liczbaPunktow; cin >> liczbaPunktow; vector<vector<unsigned long long>> tab; unsigned long long x; unsigned long long y; unsigned long long indeks = 0; for (int i = 0; i < liczbaPunktow; i++) { cin >> x; cin >> y; vector<unsigned long long> pom; pom.push_back(x); pom.push_back(y); pom.push_back(indeks++); tab.push_back(pom); } sortuj(tab, 0); unsigned long long maxY,minY,minX,maxX; minX = maxX = tab[0][0]; minY = maxY = tab[0][1]; bool ostY = false; bool pokaz = false; for (int i = 1; i < liczbaPunktow; i++) { if (minY > tab[i][1]) { cout << "NIE"<<endl; pokaz = true; break; } if (tab[i][1] > tab[i - 1][1]) { ostY = true; tab[i - 1][2] = tab[i][1] - tab[i - 1][1]; } else { if (ostY) { //TODO: Zrobić co się stanie jak było potem X tab[i-1][2]=tab[i-1][1]-tab[i][1]; } } if (!ostY) { tab[i - 1][2] = tab[i][0] - tab[i - 1][0]; } if (maxY <= tab[i][1] + tab[i][2]) maxY = tab[i][1] + tab[i][2]; if (maxX <= tab[i][0] + tab[i][2]) maxX = tab[i][0] + tab[i][2]; } tab[liczbaPunktow - 1][2] = maxY - tab[liczbaPunktow - 1][1]; unsigned long long pole = (maxY - minY) * (maxX - minX); unsigned long long polezdanych = 0; for (int i = 0; i < liczbaPunktow; i++) polezdanych += tab[i][2] * tab[i][2]; if (pokaz); else if (polezdanych == pole) { cout << "TAK "; for (int i = 0; i < liczbaPunktow; i++) cout << tab[i][2] << " "; cout<<endl; } else if (polezdanych != pole) cout << "NIE"<<endl; } return 0; } |