#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
struct point {
int x, y;
};
void print(point p) {
debug(p.x, p.y);
}
pair<long long, vector<array<int, 3>>> solve(vector<point>& p) {// k = 2
sort(p.begin(), p.end(), [&](point i, point j) {
return i.x < j.x;
});
vector<array<int, 3>> vec;
long long ret = LLONG_MAX / 3;
int mnx = p[0].x, mny = p[0].y;
int mxx = p[0].x, mxy = p[0].y;
int n = p.size();
vector<int> smnx(n), smny(n);
vector<int> smxx(n), smxy(n);
smnx[n - 1] = smxx[n - 1] = p[n - 1].x;
smny[n - 1] = smxy[n - 1] = p[n - 1].y;
for (int i = n - 2; i >= 0; --i) {
smnx[i] = min(p[i].x, smnx[i + 1]);
smxx[i] = max(p[i].x, smxx[i + 1]);
smny[i] = min(p[i].y, smny[i + 1]);
smxy[i] = max(p[i].y, smxy[i + 1]);
}
for (int i = 1; i < n; ++i) {
int mx = max({1, mxx - mnx, mxy - mny});
long long val = (long long) mx * mx;
mx = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
val += (long long) mx * mx;
if (val < ret) {
ret = val;
vec.clear();
vec.push_back({mnx, mny, max({1, mxx - mnx, mxy - mny})});
vec.push_back({smnx[i], smny[i], max({1, smxx[i] - smnx[i], smxy[i] - smny[i]})});
}
mnx = min(mnx, p[i].x);
mxx = max(mxx, p[i].x);
mny = min(mny, p[i].y);
mxy = max(mxy, p[i].y);
}
sort(p.begin(), p.end(), [&](point i, point j) {
return i.x < j.x;
});
smnx[n - 1] = smxx[n - 1] = p[n - 1].x;
smny[n - 1] = smxy[n - 1] = p[n - 1].y;
for (int i = n - 2; i >= 0; --i) {
smnx[i] = min(p[i].x, smnx[i + 1]);
smxx[i] = max(p[i].x, smxx[i + 1]);
smny[i] = min(p[i].y, smny[i + 1]);
smxy[i] = max(p[i].y, smxy[i + 1]);
}
mnx = p[0].x, mny = p[0].y;
mxx = p[0].x, mxy = p[0].y;
for (int i = 1; i < n; ++i) {
int mx = max({1, mxx - mnx, mxy - mny});
long long val = (long long) mx * mx;
mx = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
val += (long long) mx * mx;
if (val < ret) {
ret = val;
vec.clear();
vec.push_back({mnx, mny, max({1, mxx - mnx, mxy - mny})});
vec.push_back({smnx[i], smny[i], max({1, smxx[i] - smnx[i], smxy[i] - smny[i]})});
}
mnx = min(mnx, p[i].x);
mxx = max(mxx, p[i].x);
mny = min(mny, p[i].y);
mxy = max(mxy, p[i].y);
}
return {ret, vec};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<point> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
}
if (k == 1) {
int mnX = p[0].x, mxX = p[0].y;
int mnY = p[0].x, mxY = p[0].y;
for (int i = 1; i < n; ++i) {
mnX = min(mnX, p[i].x);
mxX = max(mxX, p[i].x);
mnY = min(mnY, p[i].y);
mxY = max(mxY, p[i].y);
}
assert(mxX >= mnX && mxY >= mnY);
cout << mnX << ' ' << mnY << ' ' << max({1, mxX - mnX, mxY - mnY}) << '\n';
return 0;
}
vector<array<int, 3>> vec = solve(p).second;
for (auto& it : vec) {
cout << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
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 |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
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 |
- |
