#include <bits/stdc++.h>
using namespace std;
using lint = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<lint> X(N), Y(N);
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
}
// There is a vertical or horizontal line which divides K = 3 -> {1, 2}.
// Binary search the answer L. If cuts are shaped like (|-), then we
// can greedily take big left part. If cuts are shaped like (| |), we
// brute force middle (as we can greedily take middle), precompute left part
// and right part.
//
// This takes O(N log N log MAX).
vector<array<lint, 3>> ans;
const auto SolveK1 = [&](lint L, vector<int> alive, int config) {
if (alive.empty()) return true;
lint minX = +2e9;
lint maxX = -2e9;
lint minY = +2e9;
lint maxY = -2e9;
for (auto i : alive) {
minX = min(minX, X[i]);
maxX = max(maxX, X[i]);
minY = min(minY, Y[i]);
maxY = max(maxY, Y[i]);
}
if (maxX - minX <= L && maxY - minY <= L) {
lint len = max({1ll, maxX - minX, maxY - minY});
if (config == 0) ans.push_back({minX, minY, len});
if (config == 1) ans.push_back({maxX - len, minY, len});
if (config == 2) ans.push_back({maxX - len, maxY - len, len});
if (config == 3) ans.push_back({minX, maxY - len, len});
return true;
}
return false;
};
const auto SolveK2 = [&](int L, vector<int> alive, int vert, int config) {
sort(begin(alive), end(alive), [&](int i, int j) {
if (!vert) {
return pair(Y[i], X[i]) < pair(Y[j], X[j]);
} else {
return pair(X[i], Y[i]) < pair(X[j], Y[j]);
}
});
vector<lint> prefMinX(alive.size());
vector<lint> prefMaxX(alive.size());
vector<lint> prefMinY(alive.size());
vector<lint> prefMaxY(alive.size());
vector<lint> suffMinX(alive.size());
vector<lint> suffMaxX(alive.size());
vector<lint> suffMinY(alive.size());
vector<lint> suffMaxY(alive.size());
for (int i = 0; i < int(alive.size()); i++) {
int id = alive[i];
prefMinX[i] = prefMaxX[i] = X[id];
prefMinY[i] = prefMaxY[i] = Y[id];
suffMinX[i] = suffMaxX[i] = X[id];
suffMinY[i] = suffMaxY[i] = Y[id];
}
for (int i = 1; i < int(alive.size()); i++) {
prefMinX[i] = min(prefMinX[i], prefMinX[i - 1]);
prefMaxX[i] = max(prefMaxX[i], prefMaxX[i - 1]);
prefMinY[i] = min(prefMinY[i], prefMinY[i - 1]);
prefMaxY[i] = max(prefMaxY[i], prefMaxY[i - 1]);
}
for (int i = int(alive.size()) - 2; i >= 0; i--) {
suffMinX[i] = min(suffMinX[i], suffMinX[i + 1]);
suffMaxX[i] = max(suffMaxX[i], suffMaxX[i + 1]);
suffMinY[i] = min(suffMinY[i], suffMinY[i + 1]);
suffMaxY[i] = max(suffMaxY[i], suffMaxY[i + 1]);
}
const auto CalcPref = [&](int i) {
return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
};
const auto CalcSuff = [&](int i) {
return max(suffMaxX[i] - suffMinX[i], suffMaxY[i] - suffMinY[i]);
};
vector<int> pref;
vector<int> suff = alive;
reverse(begin(suff), end(suff));
for (int i = 0; i + 1 < int(alive.size()); i++) {
pref.emplace_back(alive[i]);
suff.pop_back();
if (!(i == 0 || (vert == 0 && Y[i + 1] != Y[i]) || (vert == 1 && X[i + 1] != X[i]))) {
continue;
}
if (CalcPref(i) <= L && CalcSuff(i + 1) <= L) {
assert(SolveK1(L, pref, 2));
assert(SolveK1(L, suff, 0));
return true;
}
}
return false;
};
const auto Solve = [&](int K, lint L) {
vector<int> alive(N);
iota(begin(alive), end(alive), 0);
if (K == 1) {
ans.clear();
return SolveK1(L, alive, 0);
} else if (K == 2) {
ans.clear();
if (SolveK2(L, alive, 0, 0)) {
return true;
}
ans.clear();
if (SolveK2(L, alive, 1, 0)) {
return true;
}
}
return false;
};
lint lo = 1;
lint hi = 2e9;
while (lo < hi) {
lint md = (lo + hi) / 2;
if (Solve(K, md)) {
hi = md;
} else {
lo = md + 1;
}
}
// const auto Solve = [&](const auto &self, lint L, int k, vector<int> dead, vector<pair<int, int>> squares) -> pair<bool, vector<pair<int, int>>> {
// if (count(begin(dead), end(dead), 1) == N) {
// return {true, vector<pair<int, int>>(k, {0, 0})};
// }
// if (k == 0) {
// return {false, vector<pair<int, int>>()};
// }
// for (auto x : {minX, maxX - L}) {
// for (auto y : {minY, maxY - L}) {
// vector<int> newDead = dead;
// for (int i = 0; i < N; i++) if (!dead[i]) {
// if (x <= X[i] && X[i] <= x + L && y <= Y[i] && Y[i] <= y + L) {
// newDead[i] = 1;
// }
// }
// auto res = self(self, L, k - 1, newDead);
// if (res.first) {
// res.second.emplace_back(x, y);
// return res;
// }
// }
// }
// return {false, vector<pair<int, int>>()};
// };
// lint lo = 1, hi = 2e9;
// while (lo < hi) {
// lint md = (lo + hi) / 2;
// if (Solve(Solve, md, K, vector<int>(N, 0)).first) {
// hi = md;
// } else {
// lo = md + 1;
// }
// }
assert(Solve(K, lo));
while (ans.size() < K) {
int it = 0;
ans.push_back({lint(3e9 - it), lint(3e9 - it), 1});
it++;
}
for (int i = 0; i < K; i++) {
cout << ans[i][0] << ' ' << ans[i][1] << ' ' << ans[i][2] << '\n';
}
return 0;
}
Compilation message
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:183:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
183 | while (ans.size() < K) {
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
45 ms |
2820 KB |
Output is correct |
| 8 |
Correct |
40 ms |
2656 KB |
Output is correct |
| 9 |
Correct |
52 ms |
2656 KB |
Output is correct |
| 10 |
Correct |
41 ms |
2656 KB |
Output is correct |
| 11 |
Correct |
43 ms |
2700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
480 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
