#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Answer {
ll ans = 2e9 + 7;
vector<vector<ll>> res;
void norm(int k) {
int t = 0;
ll x = 2.5e9, y = 2.5e9;
while (res.size() < k) {
res.push_back({x, y, 1});
t += 1;
if (t & 1) {
x = -x;
}
if (t & 2) {
y = -y;
}
}
}
};
void update(pair<ll, ll> &x, ll y) {
x.first = min(x.first, y);
x.second = max(x.second, y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<ll, ll>> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
Answer ans{};
ans.ans = 2e9 + 7;
if (k >= 1) {
ll minx = 2e9, maxx = -2e9, miny = 2e9, maxy = -2e9;
for (auto &[x, y] : a) {
minx = min(minx, x);
maxx = max(maxx, x);
miny = min(miny, y);
maxy = max(maxy, y);
}
ll d = max({1LL, maxy - miny, maxx - minx});
ans.ans = d;
ans.res = {vector<ll>{minx, miny, d}};
}
if (k >= 2) {
for (int t = 0; t < 2; ++t) {
Answer now{};
sort(a.begin(), a.end());
vector<ll> mn(n + 1, 2e9), mx(n + 1, -2e9);
for (int i = n - 1; i >= 0; --i) {
mn[i] = min(mn[i + 1], a[i].second);
mx[i] = max(mx[i + 1], a[i].second);
}
ll mny = 2e9, mxy = -2e9;
for (int i = 0; i < n; ++i) {
mny = min(mny, a[i].second);
mxy = max(mxy, a[i].second);
if (i + 1 < n && a[i + 1].first != a[i].first) {
ll d = max({1LL, mxy - mny, mx[i + 1] - mn[i + 1], a[i].first - a[0].first, a.back().first - a[i + 1].first});
if (now.ans > d) {
now.ans = d;
now.res.clear();
int rx = a[i].first;
int ry = mxy;
now.res.push_back({rx - d, ry - d, d});
int lx = a[i + 1].first;
int ly = mn[i + 1];
now.res.push_back({lx, ly, d});
}
}
}
if (t == 1) {
for (auto &f : now.res) {
swap(f[0], f[1]);
}
}
if (ans.ans > now.ans) {
ans = now;
}
for (auto &[x, y]: a) {
swap(x, y);
}
}
}
if (k >= 3) {
for (int swp = 0; swp < 2; ++swp) {
for (int neg = 0; neg < 2; ++neg) {
sort(a.begin(), a.end());
Answer now{};
ll mny = 2e9, mxy = -2e9;
for (int pref = 0; pref < n - 2; ++pref) {
mny = min(mny, a[pref].second);
mxy = max(mxy, a[pref].second);
ll dnow = max({1LL, mxy - mny, a[pref].first - a[0].first});
if (a[pref + 1].first != a[pref].first) {
// case 1: sandwich
pair<ll, ll> Y{2e9, -2e9};
vector<pair<ll, ll>> suf(n + 1, pair<ll, ll>(2e9, -2e9));
for (int i = n - 1; i >= 0; --i) {
suf[i] = suf[i + 1];
update(suf[i], a[i].second);
}
for (int m = pref + 1; m + 1 < n; ++m) {
update(Y, a[m].second);
if (a[m + 1].first != a[m].first && Y.second - Y.first <= a[m].first - a[pref + 1].first) {
ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].first - a[m + 1].first});
ll dm = max({1LL, Y.second - Y.first, a[m].first - a[pref + 1].first});
ll D = max({dm, dr, dnow});
if (now.ans > D) {
now.ans = D;
now.res.clear();
now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
now.res.push_back({a[pref + 1].first, Y.first, dm});
now.res.push_back({a[m + 1].first, suf[m + 1].first, dr});
}
}
}
// case 2: not sandwich
sort(a.begin() + pref + 1, a.end(), [&](auto u, auto v) {
return u.second < v.second;
});
pair<ll, ll> X = {2e9, -2e9};
fill(suf.begin(), suf.end(), pair<ll, ll>(2e9, -2e9));
for (int i = n - 1; i >= 0; --i) {
suf[i] = suf[i + 1];
update(suf[i], a[i].first);
}
for (int m = pref + 1; m + 1 < n; ++m) {
update(X, a[m].first);
ll dm = max({1LL, X.second - X.first, a[m].second - a[pref + 1].second});
ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].second - a[m + 1].second});
if (a[m].second != a[m + 1].second) {
ll D = max({dnow, dm, dr});
if (now.ans > D) {
now.ans = D;
now.res.clear();
now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
now.res.push_back({X.first, a[m].second - dm, dm});
now.res.push_back({suf[m + 1].first, a[m + 1].second, dr});
}
}
}
sort(a.begin() + pref + 1, a.end());
}
if (now.ans < ans.ans) {
ans = now;
for (auto &f : ans.res) {
if (neg) {
f[0] = -f[0];
}
if (swp) {
swap(f[0], f[1]);
}
}
}
}
for (auto &[x, y] : a) {
x = -x;
}
}
for (auto &[x, y] : a) {
swap(x, y);
}
}
}
ans.norm(k);
for (auto &t : ans.res) {
for (auto x : t) {
cout << x << " ";
}
cout << '\n';
}
return 0;
}
Compilation message
izvanzemaljci.cpp: In member function 'void Answer::norm(int)':
izvanzemaljci.cpp:13:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
13 | while (res.size() < k) {
| ~~~~~~~~~~~^~~
| # |
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 |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1884 KB |
Output is correct |
| 8 |
Correct |
16 ms |
1884 KB |
Output is correct |
| 9 |
Correct |
14 ms |
1880 KB |
Output is correct |
| 10 |
Correct |
16 ms |
1884 KB |
Output is correct |
| 11 |
Correct |
17 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
30 ms |
3408 KB |
Output is correct |
| 11 |
Correct |
30 ms |
3416 KB |
Output is correct |
| 12 |
Correct |
30 ms |
3420 KB |
Output is correct |
| 13 |
Correct |
30 ms |
3408 KB |
Output is correct |
| 14 |
Correct |
31 ms |
3416 KB |
Output is correct |
| 15 |
Correct |
30 ms |
3416 KB |
Output is correct |
| 16 |
Correct |
30 ms |
3412 KB |
Output is correct |
| 17 |
Correct |
27 ms |
3268 KB |
Output is correct |
| 18 |
Correct |
27 ms |
3164 KB |
Output is correct |
| 19 |
Correct |
24 ms |
2924 KB |
Output is correct |
| 20 |
Correct |
27 ms |
3104 KB |
Output is correct |
| 21 |
Correct |
38 ms |
3672 KB |
Output is correct |
| 22 |
Correct |
31 ms |
3420 KB |
Output is correct |
| 23 |
Correct |
30 ms |
3420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
158 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
