#include <bits/stdc++.h>
using namespace std;
using lli = long long;
pair<vector<int>, lli> calc(vector<pair<int, int>> points) {
map<int, vector<pair<int, int>>> batch;
for (auto [x, y]: points)
batch[x].emplace_back(x, y);
multiset<int> xs, ys;
for (auto [x, y]: points) {
xs.insert(x);
ys.insert(y);
}
int d = max(*xs.rbegin() - *xs.begin(), *ys.rbegin() - *ys.begin());
d = max(d, 1);
int mx_x = 0, mn_x = 1e9, mx_y = 0, mn_y = 1e9;
vector<int> ans{*xs.begin(), *ys.begin(), d, (int)2e9, (int)2e9, 1}; lli best = 1LL*d*d + 1;
for (auto [k, abas]: batch) {
for (auto [x, y]: abas) {
assert(xs.find(x) != xs.end());
assert(ys.find(y) != ys.end());
if (xs.empty()) break;
mx_x = max(mx_x, x); mn_x = min(mn_x, x);
mx_y = max(mx_y, y); mn_y = min(mn_y, y);
xs.erase(xs.find(x)); ys.erase(ys.find(y));
}
if (xs.empty()) break;
int d1 = max(mx_x - mn_x, mx_y - mn_y);
int d2 = max(*xs.rbegin() - *xs.begin(), *ys.rbegin() - *ys.begin());
d1 = max(d1, 1);
d2 = max(d2, 1);
lli cost1 = 1LL*d1*d1;
lli cost2 = 1LL*d2*d2;
if (cost1 + cost2 < best) {
best = cost1 + cost2;
if (mn_x + d1 > k) {
if (k - d1 >= 0) ans = vector<int>{k - d1, mn_y, d1, *xs.begin(), *ys.begin(), d2};
}
else ans = vector<int>{mn_x, mn_y, d1, *xs.begin(), *ys.begin(), d2};
}
}
return {ans, best};
}
int main() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> points(n);
for (auto &[x, y]: points)
cin >> x >> y;
if (k == 1) {
multiset<int> xs, ys;
for (auto [x, y]: points) {
xs.insert(x);
ys.insert(y);
}
int d2 = max(*xs.rbegin() - *xs.begin(), *ys.rbegin() - *ys.begin());
d2 = max(d2, 1);
cout << *xs.begin() << " " << *ys.begin() << " " << d2 << "\n";
return 0;
}
if (n == 1) {
cout << points[0].first << " " << points[0].second << " 1\n";
cout << points[0].first + 2 << " " << points[0].second + 2 << " 1\n";
return 0;
}
auto [ans1, best1] = calc(points);
for (auto &[x, y]: points) swap(x, y);
auto [ans2, best2] = calc(points);
if (best2 < best1) {
swap(ans2, ans1);
swap(ans1[0], ans1[1]);
swap(ans1[3], ans1[4]);
}
for (int i = 0; i < 6; ++i)
cout << ans1[i] << (i == 2 ? "\n" : " ");
cout << "\n";
}
Compilation message
izvanzemaljci.cpp: In function 'std::pair<std::vector<int>, long long int> calc(std::vector<std::pair<int, int> >)':
izvanzemaljci.cpp:8:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
8 | for (auto [x, y]: points)
| ^
izvanzemaljci.cpp:12:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
12 | for (auto [x, y]: points) {
| ^
izvanzemaljci.cpp:22:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for (auto [k, abas]: batch) {
| ^
izvanzemaljci.cpp:23:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
23 | for (auto [x, y]: abas) {
| ^
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto &[x, y]: points)
| ^
izvanzemaljci.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for (auto [x, y]: points) {
| ^
izvanzemaljci.cpp:83:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | auto [ans1, best1] = calc(points);
| ^
izvanzemaljci.cpp:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | for (auto &[x, y]: points) swap(x, y);
| ^
izvanzemaljci.cpp:85:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [ans2, best2] = calc(points);
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
436 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
103 ms |
11632 KB |
Output is correct |
| 8 |
Correct |
95 ms |
11856 KB |
Output is correct |
| 9 |
Correct |
102 ms |
11688 KB |
Output is correct |
| 10 |
Correct |
99 ms |
11856 KB |
Output is correct |
| 11 |
Correct |
99 ms |
11088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
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 |
2 ms |
604 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
