#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 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, -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]));
ans_nw.add(Point(a[i].x - side1, pr_mn[i + 1]), side1);
int side2 = max(1LL, 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;
}
Answer split2(vector<Point> a, long long mn_x, long long mx_x, long long mn_y, long long mx_y) {
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(min(a[0].x, a[i + 1].x - 1 - side1), pr_mn[i + 1]);
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(min(a[i + 1].x, max(a[i].x + 1, a[n - 1].x - side1)), suf_mn[i + 1]);
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 (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 (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 (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 (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 (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 = -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) {
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
16 ms |
1884 KB |
Output is correct |
| 8 |
Correct |
15 ms |
1884 KB |
Output is correct |
| 9 |
Correct |
15 ms |
2136 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1880 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
