#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;
struct Point{
ll x, y;
void read(){
cin >> x >> y;
return;
}
} p[M];
bool OnX (Point a, Point b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool OnY (Point a, Point b){
if(a.y == b.y) return a.x < b.y;
return a.y < b.y;
}
ll n, k, mx[M], my[M], mnx[M], mny[M];
void init(){
mnx[0] = mny[0] = inf;
mx[0] = my[0] = -inf;
for(int i = 1; i <= n; ++i){
mnx[i] = min(mnx[i - 1], p[i].x);
mx[i] = max(mx[i - 1], p[i].x);
mny[i] = min(mny[i - 1], p[i].y);
my[i] = max(my[i - 1], p[i].y);
}
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i) p[i].read();
if(k == 1) init(), cout << mnx[n] << " " << mny[n] << " " << max(1ll, max(mx[n] - mnx[n], my[n] - mny[n])) << endl;
else if(k == 2){
if(n == 1){
cout << p[1].x << " " << p[1].y << " " << 1 << endl;
cout << inf << " " << inf << " " << 1 << endl;
return 0;
}
if(n == 2){
sort(p + 1, p + n + 1, OnX);
cout << p[1].x - 1 << " " << p[1].y - 1 << " " << 1 << endl;
cout << p[2].x << " " << p[2].y << " " << 1 << endl;
return 0;
}
ll ans = 1e18; vector < pair < pair <ll,ll>, ll > > v;
sort(p + 1, p + n + 1, OnX);
init();
ll a = inf, b = -inf, c = inf, d = -inf;
for(int i = n; i; --i){
if(i < n && mnx[i] != a){
ll x = max((mx[i] - mnx[i], my[i] - mny[i]) * max(mx[i] - mnx[i], my[i] - mny[i]), max(b - a, d - c) * max(b - a, d - c));
if(x < ans){
ans = x;
v.clear();
v.pb({{mnx[i], mny[i]}, max(mx[i] - mnx[i], my[i] - mny[i])});
v.pb({{a, c}, max(d - c, b - a)});
}
}
a = min(a, p[i].x);
b = max(b, p[i].x);
c = min(c, p[i].y);
d = max(d, p[i].y);
}
sort(p + 1, p + n + 1, OnY);
init();
a = inf; b = -inf; c = inf; d = -inf;
for(int i = n; i; --i){
if(i < n && mny[i] != c){
ll x = max((mx[i] - mnx[i], my[i] - mny[i]) * max(mx[i] - mnx[i], my[i] - mny[i]), max(b - a, d - c) * max(b - a, d - c));
if(x < ans){
ans = x;
v.clear();
v.pb({{mnx[i], mny[i]}, max(mx[i] - mnx[i], my[i] - mny[i])});
v.pb({{a, c}, max(d - c, b - a)});
}
}
a = min(a, p[i].x);
b = max(b, p[i].x);
c = min(c, p[i].y);
d = max(d, p[i].y);
}
int cnt = 0;
for(auto i : v){ ++cnt;
if(i.S == 0){
if(cnt == 1) ++i.S, --i.F.F, --i.F.S;
else ++i.S;
}
cout << i.F.F << " " << i.F.S << " " << i.S << endl;
}
}
return 0;
}
Compilation message
cigle.cpp: In function 'int main()':
cigle.cpp:82:35: warning: left operand of comma operator has no effect [-Wunused-value]
82 | ll x = max((mx[i] - mnx[i], my[i] - mny[i]) * max(mx[i] - mnx[i], my[i] - mny[i]), max(b - a, d - c) * max(b - a, d - c));
| ~~~~~~^~~~~~~~
cigle.cpp:106:35: warning: left operand of comma operator has no effect [-Wunused-value]
106 | ll x = max((mx[i] - mnx[i], my[i] - mny[i]) * max(mx[i] - mnx[i], my[i] - mny[i]), max(b - a, d - c) * max(b - a, d - c));
| ~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
