#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1e9 + 7;
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 get_ans(int n, vector<Point> a) {
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, 0), suf_mn(n + 1, inf), suf_mx(n + 1, 0);
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(1, max(a[i].x - a[0].x, pr_mx[i + 1] - pr_mn[i + 1]));
ans_nw.add(Point(a[i].x - side1, pr_mn[i + 1]), side1);
int side2 = max(1, max(a[n - 1].x - a[i + 1].x, suf_mx[i + 1] - suf_mn[i + 1]));
ans_nw.add(Point(a[i + 1].x, suf_mn[i + 1]), side2);
if (ans_nw < ans) {
ans = ans_nw;
}
}
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 = 0, mn_y = inf, mx_y = 0;
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(1, max(mx_x - mn_x, mx_y - mn_y)) << '\n';
} else if (k == 2) {
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);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Integer 0 violates the range [1, 2*10^9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
