제출 #997952

#제출 시각아이디문제언어결과실행 시간메모리
997952arbuzickIzvanzemaljci (COI21_izvanzemaljci)C++17
0 / 100
1 ms348 KiB
#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, -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(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 = -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(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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...