#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr long long inf = (long long)1e18 + 7;
constexpr long long vl = 3000000001;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) {
x = _x, y = _y;
}
};
struct Answer {
vector<pair<Point, int>> squares;
int mx;
Answer() {
mx = 0;
}
void add(Point p, int side) {
squares.emplace_back(p, side);
mx = max(mx, side);
}
bool operator<(Answer b) {
return mx < b.mx;
}
};
Answer split2(vector<Point> a, long long mn_x, long long mx_x, long long mn_y, long long mx_y) {
auto check = [&](Answer ans) -> bool {
for (int i = 0; i < (int)ans.squares.size(); ++i) {
if (ans.squares[i].first.x <= mn_x || ans.squares[i].first.x + ans.squares[i].second >= mx_x) {
return false;
}
if (ans.squares[i].first.y < mn_y || ans.squares[i].first.y + ans.squares[i].second >= mx_y) {
return false;
}
}
return true;
};
int n = a.size();
sort(a.begin(), a.end(), [&](Point a, Point b) -> bool {
return a.x < b.x;
});
vector<int> pr_mn(n + 1, inf), pr_mx(n + 1, -inf), suf_mn(n + 1, inf), suf_mx(n + 1, -inf);
for (int i = 0; i < n; ++i) {
pr_mn[i + 1] = min(pr_mn[i], a[i].y);
pr_mx[i + 1] = max(pr_mx[i], a[i].y);
}
for (int i = n - 1; i >= 0; --i) {
suf_mn[i] = min(suf_mn[i + 1], a[i].y);
suf_mx[i] = max(suf_mx[i + 1], a[i].y);
}
Answer ans;
ans.add(Point(0, 0), inf);
for (int i = 0; i + 1 < n; ++i) {
if (a[i].x == a[i + 1].x) {
continue;
}
Answer ans_nw;
int side1 = max(1LL, max(a[i].x - a[0].x, pr_mx[i + 1] - pr_mn[i + 1]));
Point p1(a[i].x - side1, pr_mn[i + 1]);
if (p1.x <= mn_x) {
p1.x = a[i + 1].x - 1 - side1;
if (p1.x <= mn_x) {
continue;
}
}
if (p1.y + side1 >= mx_y) {
p1.y = pr_mx[i + 1] - side1;
}
ans_nw.add(p1, side1);
int side2 = max(1LL, max(a[n - 1].x - a[i + 1].x, suf_mx[i + 1] - suf_mn[i + 1]));
Point p2(a[i + 1].x, suf_mn[i + 1]);
if (p2.x + side2 >= mx_x) {
p2.x = max(a[i].x + 1, a[n - 1].x - side2);
if (p2.x + side2 >= mx_x) {
continue;
}
}
if (p2.y + side2 >= mx_y) {
p2.y = suf_mx[i + 1] - side2;
}
ans_nw.add(p2, side2);
if (check(ans_nw) && ans_nw < ans) {
ans = ans_nw;
}
}
int side = max(1LL, max(a[n - 1].x - a[0].x, pr_mx[n] - pr_mn[n]));
Point p(a[0].x, pr_mn[n]);
if (p.x + side >= mx_x) {
p.x = a[n - 1].x - side;
}
if (p.y + side >= mx_y) {
p.y = pr_mx[n] - side;
}
Answer ans_nw;
ans_nw.add(p, side);
if (p.x - 2 >= mn_x && p.y - 2 >= mn_y) {
ans_nw.add(Point(p.x - 2, p.y - 2), 1);
if (check(ans_nw) && ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x - 2 >= mn_x && p.y + side + 2 <= mx_y) {
ans_nw.add(Point(p.x - 2, p.y + side + 1), 1);
if (check(ans_nw) && ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x + side + 2 <= mx_x && p.y - 2 >= mn_y) {
ans_nw.add(Point(p.x + side + 1, p.y - 2), 1);
if (check(ans_nw) && ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x + side + 2 <= mx_x && p.y + side + 2 <= mx_y) {
ans_nw.add(Point(p.x + side + 1, p.y + side + 1), 1);
if (check(ans_nw) && ans_nw < ans) {
ans = ans_nw;
}
}
return ans;
}
Answer get_ans(int n, vector<Point> a) {
auto check = [&](Answer ans) -> bool {
for (int i = 0; i < k; ++i) {
if (ans.squares[i].first.x < -vl || ans.squares[i].first.x > vl) {
return false;
}
if (ans.squares[i].first.y < -vl || ans.squares[i].first.y > vl) {
return false;
}
}
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
if (min(ans.squares[i].first.x + ans.squares[i].second, ans.squares[j].first.x + ans.squares[j].second) >= max(ans.squares[i].first.x, ans.squares[j].first.x) &&
min(ans.squares[i].first.y + ans.squares[i].second, ans.squares[j].first.y + ans.squares[i].second) >= max(ans.squares[i].first.y, ans.squares[j].first.y)) {
return false;
}
}
}
return true;
};
sort(a.begin(), a.end(), [&](Point a, Point b) -> bool {
return a.x < b.x;
});
Answer ans;
ans.add(Point(0, 0), inf);
int mn_y = inf, mx_y = -inf;
for (int i = 0; i < n; ++i) {
mn_y = min(mn_y, a[i].y);
mx_y = max(mx_y, a[i].y);
if (i == n - 1 || a[i].x == a[i + 1].x) {
continue;
}
vector<Point> b;
for (int j = i + 1; j < n; ++j) {
b.push_back(a[j]);
}
Answer ans1_ans = split2(b, a[i].x, vl, -vl, vl);
for (int j = 0; j < (int)b.size(); ++j) {
swap(b[j].x, b[j].y);
}
Answer ans2_ans = split2(b, -vl, vl, a[i].x, vl);
for (int i = 0; i < 2; ++i) {
swap(ans2_ans.squares[i].first.x, ans2_ans.squares[i].first.y);
}
if (ans2_ans < ans1_ans) {
ans1_ans = ans2_ans;
}
int side = max(1LL, max(a[i].x - a[0].x, mx_y - mn_y));
ans1_ans.add(Point(a[i].x - side, mn_y), side);
if (ans1_ans < ans) {
ans = ans1_ans;
}
}
int side = max(1LL, max(a[n - 1].x - a[0].x, mx_y - mn_y));
Point p(a[0].x, mn_y);
Answer ans_nw;
ans_nw.add(p, side);
if (p.x - 4 >= -vl && p.y - 4 >= -vl) {
ans_nw.add(Point(p.x - 2, p.y - 2), 1);
ans_nw.add(Point(p.x - 4, p.y - 4), 1);
if (ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x - 4 >= -vl && p.y + 4 <= vl) {
ans_nw.add(Point(p.x - 2, p.y + 1), 1);
ans_nw.add(Point(p.x - 4, p.y + 3), 1);
if (ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x + 4 <= vl && p.y - 4 >= vl) {
ans_nw.add(Point(p.x + 1, p.y - 2), 1);
ans_nw.add(Point(p.x + 3, p.y - 4), 1);
if (ans_nw < ans) {
ans = ans_nw;
}
} else if (p.x + 4 <= vl && p.y + 4 <= vl) {
ans_nw.add(Point(p.x + 1, p.y + 1), 1);
ans_nw.add(Point(p.x + 3, p.y + 3), 1);
if (ans_nw < ans) {
ans = ans_nw;
}
}
mn_y = inf, mx_y = -inf;
for (int i = n - 1; i > 0; --i) {
mn_y = min(mn_y, a[i].y);
mx_y = max(mx_y, a[i].y);
if (i == 0 || a[i].x == a[i - 1].x) {
continue;
}
vector<Point> b;
for (int j = 0; j < i; ++j) {
b.push_back(a[j]);
}
Answer ans1_ans = split2(b, -vl, a[i].x, -vl, vl);
for (int j = 0; j < (int)b.size(); ++j) {
swap(b[j].x, b[j].y);
}
Answer ans2_ans = split2(b, -vl, vl, -vl, a[i].x);
for (int i = 0; i < 2; ++i) {
swap(ans2_ans.squares[i].first.x, ans2_ans.squares[i].first.y);
}
if (ans2_ans < ans1_ans) {
ans1_ans = ans2_ans;
}
int side = max(1LL, max(a[n - 1].x - a[i].x, mx_y - mn_y));
ans1_ans.add(Point(a[i].x, mn_y), side);
if (ans1_ans < ans) {
ans = ans1_ans;
}
}
assert(check(ans));
return ans;
}
void solve() {
int n, k;
cin >> n >> k;
vector<Point> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].x >> a[i].y;
}
if (k == 1) {
int mn_x = inf, mx_x = -inf, mn_y = inf, mx_y = -inf;
for (int i = 0; i < n; ++i) {
mn_x = min(mn_x, a[i].x);
mx_x = max(mx_x, a[i].x);
mn_y = min(mn_y, a[i].y);
mx_y = max(mx_y, a[i].y);
}
cout << mn_x << ' ' << mn_y << ' ' << max(1LL, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
} else if (k == 2) {
auto ans1 = split2(a, -vl, vl, -vl, vl);
for (int i = 0; i < n; ++i) {
swap(a[i].x, a[i].y);
}
auto ans2 = split2(a, -vl, vl, -vl, vl);
for (int i = 0; i < k; ++i) {
swap(ans2.squares[i].first.x, ans2.squares[i].first.y);
}
if (ans1 < ans2) {
for (int i = 0; i < k; ++i) {
cout << ans1.squares[i].first.x << ' ' << ans1.squares[i].first.y << ' ' << ans1.squares[i].second << '\n';
}
} else {
for (int i = 0; i < k; ++i) {
cout << ans2.squares[i].first.x << ' ' << ans2.squares[i].first.y << ' ' << ans2.squares[i].second << '\n';
}
}
} else if (k == 3) {
auto ans1 = get_ans(n, a);
for (int i = 0; i < n; ++i) {
swap(a[i].x, a[i].y);
}
auto ans2 = get_ans(n, a);
for (int i = 0; i < k; ++i) {
swap(ans2.squares[i].first.x, ans2.squares[i].first.y);
}
auto check = [&](Answer ans) -> bool {
for (int i = 0; i < k; ++i) {
if (ans.squares[i].first.x < -vl || ans.squares[i].first.x > vl) {
return false;
}
if (ans.squares[i].first.y < -vl || ans.squares[i].first.y > vl) {
return false;
}
}
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
if (min(ans.squares[i].first.x + ans.squares[i].second, ans.squares[j].first.x + ans.squares[j].second) >= max(ans.squares[i].first.x, ans.squares[j].first.x) &&
min(ans.squares[i].first.y + ans.squares[i].second, ans.squares[j].first.y + ans.squares[i].second) >= max(ans.squares[i].first.y, ans.squares[j].first.y)) {
return false;
}
}
}
return true;
};
// assert(check(ans1));
// assert(check(ans2));
if (ans1 < ans2) {
for (int i = 0; i < k; ++i) {
cout << ans1.squares[i].first.x << ' ' << ans1.squares[i].first.y << ' ' << ans1.squares[i].second << '\n';
}
} else {
for (int i = 0; i < k; ++i) {
cout << ans2.squares[i].first.x << ' ' << ans2.squares[i].first.y << ' ' << ans2.squares[i].second << '\n';
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Compilation message
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:132:29: error: 'k' was not declared in this scope
132 | for (int i = 0; i < k; ++i) {
| ^
izvanzemaljci.cpp:140:29: error: 'k' was not declared in this scope
140 | for (int i = 0; i < k; ++i) {
| ^
