제출 #998075

#제출 시각아이디문제언어결과실행 시간메모리
998075arbuzickIzvanzemaljci (COI21_izvanzemaljci)C++17
26 / 100
320 ms6744 KiB
#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 < 3; ++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 < 3; ++i) { for (int j = i + 1; j < 3; ++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; }
#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...