#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 MAX).
vector<int> sortByX(N);
vector<int> sortByY(N);
iota(begin(sortByX), end(sortByX), 0);
iota(begin(sortByY), end(sortByY), 0);
sort(begin(sortByX), end(sortByX), [&](int i, int j) {
return pair(X[i], Y[i]) < pair(X[j], Y[j]);
});
sort(begin(sortByY), end(sortByY), [&](int i, int j) {
return pair(Y[i], X[i]) < pair(Y[j], X[j]);
});
vector<int> posInSortByX(N);
vector<int> posInSortByY(N);
for (int i = 0; i < N; i++) {
posInSortByX[sortByX[i]] = i;
posInSortByY[sortByY[i]] = i;
}
const auto CountingSort = [&](vector<int> &a, const vector<int> &sorted, const vector<int> &pos) {
static vector<int> res(N);
fill(begin(res), end(res), 0);
for (auto i : a) {
res[pos[i]] = 1;
}
a.clear();
for (int i = 0; i < N; i++) {
if (res[i]) {
a.emplace_back(sorted[i]);
}
}
};
vector<array<lint, 3>> ans;
const auto SolveK1 = [&](lint L, const vector<int> &alive, int config, int trace) {
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 (trace == 1 && config == 0) ans.push_back({minX, minY, len});
if (trace == 1 && config == 1) ans.push_back({maxX - len, minY, len});
if (trace == 1 && config == 2) ans.push_back({maxX - len, maxY - len, len});
if (trace == 1 && config == 3) ans.push_back({minX, maxY - len, len});
return true;
}
return false;
};
const auto SolveK2 = [&](int L, vector<int> alive, int vert, int conf, int trace) {
if (alive.empty()) return true;
if (!vert) {
CountingSort(alive, sortByY, posInSortByY);
} else {
CountingSort(alive, sortByX, posInSortByX);
}
static vector<lint> prefMinX(N);
static vector<lint> prefMaxX(N);
static vector<lint> prefMinY(N);
static vector<lint> prefMaxY(N);
static vector<lint> suffMinX(N);
static vector<lint> suffMaxX(N);
static vector<lint> suffMinY(N);
static vector<lint> suffMaxY(N);
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) -> lint {
if (i < 0 || i >= alive.size()) return 0;
return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
};
const auto CalcSuff = [&](int i) -> lint {
if (i < 0 || i >= alive.size()) return 0;
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 < int(alive.size()); i++) {
pref.emplace_back(alive[i]);
suff.pop_back();
if (!(i + 1 == alive.size() ||
(vert == 0 && Y[alive[i + 1]] != Y[alive[i]]) ||
(vert == 1 && X[alive[i + 1]] != X[alive[i]]))) {
continue;
}
if (CalcPref(i) <= L && CalcSuff(i + 1) <= L) {
if (vert == 1 && conf == 0) {
assert(SolveK1(L, pref, 2, trace));
assert(SolveK1(L, suff, 3, trace));
}
if (vert == 1 && conf == 1) {
assert(SolveK1(L, pref, 1, trace));
assert(SolveK1(L, suff, 0, trace));
}
if (vert == 0 && conf == 0) {
assert(SolveK1(L, pref, 2, trace));
assert(SolveK1(L, suff, 2, trace));
}
if (vert == 0 && conf == 1) {
assert(SolveK1(L, pref, 3, trace));
assert(SolveK1(L, suff, 0, trace));
}
// assert(SolveK1(L, pref, 2, trace));
// assert(SolveK1(L, suff, 0, trace));
return true;
}
}
return false;
};
const auto SolveK3 = [&](lint L, vector<int> alive, int vert, int trace) {
if (!vert) {
CountingSort(alive, sortByY, posInSortByY);
} else {
CountingSort(alive, sortByX, posInSortByX);
}
static vector<lint> prefMinX(N);
static vector<lint> prefMaxX(N);
static vector<lint> prefMinY(N);
static vector<lint> prefMaxY(N);
static vector<lint> suffMinX(N);
static vector<lint> suffMaxX(N);
static vector<lint> suffMinY(N);
static vector<lint> suffMaxY(N);
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) -> lint {
if (i < 0 || i >= alive.size()) return 0;
return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
};
const auto CalcSuff = [&](int i) -> lint {
if (i < 0 || i >= alive.size()) return 0;
return max(suffMaxX[i] - suffMinX[i], suffMaxY[i] - suffMinY[i]);
};
// Configuration: |-
int last = -1;
for (int i = 0; i < int(alive.size()); i++) {
if (!(i + 1 == alive.size() ||
(vert == 0 && Y[alive[i + 1]] != Y[alive[i]]) ||
(vert == 1 && X[alive[i + 1]] != X[alive[i]]))) {
continue;
}
if (CalcPref(i) <= L) {
last = i;
}
}
if (last != -1) {
vector<int> other;
for (int i = last + 1; i < int(alive.size()); i++) {
other.emplace_back(alive[i]);
}
if (SolveK2(L, other, 1 - vert, 1, trace)) {
if (trace) {
other.clear();
for (int i = 0; i <= last; i++) {
other.emplace_back(alive[i]);
}
SolveK1(L, other, 2, trace);
}
return true;
}
}
// Configuration: -|
last = -1;
for (int i = int(alive.size()) - 1; i >= 0; i--) {
if (!(i == 0 ||
(vert == 0 && Y[alive[i - 1]] != Y[alive[i]]) ||
(vert == 1 && X[alive[i - 1]] != X[alive[i]]))) {
continue;
}
if (CalcSuff(i) <= L) {
last = i;
}
}
if (last != -1) {
vector<int> other;
for (int i = 0; i < last; i++) {
other.emplace_back(alive[i]);
}
if (SolveK2(L, other, 1 - vert, 0, trace)) {
if (trace) {
other.clear();
for (int i = last; i < int(alive.size()); i++) {
other.emplace_back(alive[i]);
}
SolveK1(L, other, 0, trace);
}
return true;
}
}
// Configuration: | |
for (int i = 0; i < int(alive.size()); i++) {
lint minX = X[alive[i]];
lint maxX = X[alive[i]];
lint minY = Y[alive[i]];
lint maxY = Y[alive[i]];
if (!(i == 0 ||
(vert == 0 && Y[alive[i - 1]] != Y[alive[i]]) ||
(vert == 1 && X[alive[i - 1]] != X[alive[i]]))) {
continue;
}
for (int j = i; j < int(alive.size()); j++) {
minX = min(minX, X[alive[j]]);
maxX = max(maxX, X[alive[j]]);
minY = min(minY, Y[alive[j]]);
maxY = max(maxY, Y[alive[j]]);
if (!(j + 1 == alive.size() ||
(vert == 0 && Y[alive[j + 1]] != Y[alive[j]]) ||
(vert == 1 && X[alive[j + 1]] != X[alive[j]]))) {
continue;
}
if ((vert == 0 && maxX - minX <= maxY - minY && maxY - minY <= L) ||
(vert == 1 && maxY - minY <= maxX - minX && maxX - minX <= L)) {
if (CalcPref(i - 1) <= L && CalcSuff(j + 1) <= L) {
if (trace) {
vector<int> a, b, c;
for (int x = 0; x < int(alive.size()); x++) {
if (x < i) a.emplace_back(alive[x]);
else if (x > j) c.emplace_back(alive[x]);
else b.emplace_back(alive[x]);
}
assert(SolveK1(L, a, 2, trace));
assert(SolveK1(L, b, 0, trace));
assert(SolveK1(L, c, 0, trace));
}
return true;
}
}
}
}
return false;
// deque<pair<lint, int>> minQue;
// deque<pair<lint, int>> maxQue;
// const auto CanInsert = [&](int id) {
// if (minQue.empty() || maxQue.empty()) return true;
// lint val;
// if (vert == 0) {
// // horizontal, keep minX and maxX
// val = X[id];
// } else {
// // vertical, keep minY and maxY
// val = Y[id];
// }
// if (max(maxQue.front().first, val) - min(minQue.front().first, val) <= L) {
// return true;
// }
// };
// for (int i = 0, j = -1; i < int(alive.size()); i++) {
// while (j + 1 < int(alive.size()) &&
// (vert == 0 ? (Y[alive[j + 1]] - Y[alive[i]]) : (X[alive[j + 1]] - X[alive[i]])) <= L &&
// CanInsert(alive[j + 1])) {
// Insert(alive[j++]);
// }
// if (CalcPref(i - 1) <= L && CalcSuff(j + 1) <= L) {
// }
// Erase(alive[i]);
// }
};
const auto Solve = [&](int K, lint L, int trace) {
vector<int> alive(N);
iota(begin(alive), end(alive), 0);
if (K == 1) {
ans.clear();
return SolveK1(L, alive, 0, trace);
} else if (K == 2) {
ans.clear();
if (SolveK2(L, alive, 0, 0, trace)) {
return true;
}
ans.clear();
if (SolveK2(L, alive, 1, 0, trace)) {
return true;
}
} else if (K == 3) {
ans.clear();
if (SolveK3(L, alive, 0, trace)) {
return true;
}
ans.clear();
if (SolveK3(L, alive, 1, trace)) {
return true;
}
}
return false;
};
lint lo = 1;
lint hi = 2e9;
while (lo < hi) {
lint md = (lo + hi) / 2;
if (Solve(K, md, 0)) {
hi = md;
} else {
lo = md + 1;
}
}
assert(Solve(K, lo, 1));
int it = 0;
while (ans.size() < K) {
ans.push_back({lint(-3e9 + 2 * it), lint(3e9), 1});
it++;
}
const auto NotIntersect = [&](vector<array<lint, 3>> sq) {
for (int i = 0; i < int(sq.size()); i++) {
for (int j = 0; j < int(sq.size()); j++) if (i != j) {
for (auto x : {sq[j][0], sq[j][0] + sq[j][2]}) {
for (auto y : {sq[j][1], sq[j][1] + sq[j][2]}) {
lint minX = sq[i][0];
lint maxX = sq[i][0] + sq[i][2];
lint minY = sq[i][1];
lint maxY = sq[i][1] + sq[i][2];
if (minX <= x && x <= maxX && minY <= y && y <= maxY) {
return false;
}
}
}
}
}
return true;
};
// if (K == 3) {
// vector<int> who(N);
// const auto Dfs = [&](const auto &self, int u) -> lint {
// if (u == N) {
// vector<int> a, b, c;
// return 1;
// }
// pair<lint, vector<array<lint, 3>>> best = {4e9, {}};
// who[u] = 0;
// best = min(best, self(self, u + 1));
// who[u] = 1;
// best = min(best, self(self, u + 1));
// who[u] = 2;
// best = min(best, self(self, u + 1));
// return best;
// };
// }
assert(NotIntersect(ans));
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 lambda function:
izvanzemaljci.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | if (i < 0 || i >= alive.size()) return 0;
| ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if (i < 0 || i >= alive.size()) return 0;
| ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | if (!(i + 1 == alive.size() ||
| ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:205:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | if (i < 0 || i >= alive.size()) return 0;
| ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:209:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | if (i < 0 || i >= alive.size()) return 0;
| ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | if (!(i + 1 == alive.size() ||
| ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:291:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
291 | if (!(j + 1 == alive.size() ||
| ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:393: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]
393 | while (ans.size() < K) {
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
70 ms |
3836 KB |
Output is correct |
| 8 |
Correct |
79 ms |
3816 KB |
Output is correct |
| 9 |
Correct |
72 ms |
3800 KB |
Output is correct |
| 10 |
Correct |
71 ms |
3808 KB |
Output is correct |
| 11 |
Correct |
71 ms |
3808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
308 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
460 KB |
Output is correct |
| 2 |
Correct |
72 ms |
484 KB |
Output is correct |
| 3 |
Correct |
92 ms |
460 KB |
Output is correct |
| 4 |
Correct |
67 ms |
580 KB |
Output is correct |
| 5 |
Correct |
88 ms |
460 KB |
Output is correct |
| 6 |
Correct |
96 ms |
460 KB |
Output is correct |
| 7 |
Correct |
84 ms |
580 KB |
Output is correct |
| 8 |
Correct |
66 ms |
480 KB |
Output is correct |
| 9 |
Correct |
51 ms |
460 KB |
Output is correct |
| 10 |
Correct |
112 ms |
484 KB |
Output is correct |
| 11 |
Correct |
70 ms |
484 KB |
Output is correct |
| 12 |
Runtime error |
91 ms |
756 KB |
Execution killed with signal 6 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
488 KB |
Output is correct |
| 2 |
Correct |
85 ms |
484 KB |
Output is correct |
| 3 |
Correct |
63 ms |
476 KB |
Output is correct |
| 4 |
Correct |
80 ms |
460 KB |
Output is correct |
| 5 |
Correct |
89 ms |
480 KB |
Output is correct |
| 6 |
Correct |
89 ms |
480 KB |
Output is correct |
| 7 |
Correct |
51 ms |
492 KB |
Output is correct |
| 8 |
Correct |
49 ms |
460 KB |
Output is correct |
| 9 |
Correct |
83 ms |
496 KB |
Output is correct |
| 10 |
Correct |
85 ms |
480 KB |
Output is correct |
| 11 |
Correct |
93 ms |
460 KB |
Output is correct |
| 12 |
Correct |
106 ms |
476 KB |
Output is correct |
| 13 |
Correct |
97 ms |
460 KB |
Output is correct |
| 14 |
Execution timed out |
3070 ms |
15100 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
