#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e18+10;
pair<pair<int,int>,int> sqr(int x0, int x1, int y0, int y1) {
int l = max({(int) 1,x1-x0,y1-y0});
return mp(mp(x0,y0),l);
}
int32_t main() {
// #ifndef ONLINE_JUDGE
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
// #endif
int n,k;
cin >> n >> k;
if(k == 1) {
int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
for(int i = 0; i < n; i++) {
int x,y;
cin >> x >> y;
minx = min(x,minx);
maxx = max(x,maxx);
miny = min(y,miny);
maxy = max(y,maxy);
}
auto a = sqr(minx,maxx,miny,maxy);
cout << a.fr.fr << " " << a.fr.sc << " " << a.sc << endl;
}
else if(k == 2) {
vector<pair<pair<int,int>,int>> ansv;
int ans = inf;
vector<pair<int,int>> pts;
for(int i = 0; i < n; i++) {
int x,y;
cin >> x >> y;
pts.pb(mp(x,y));
}
{
sort(all(pts));
vector<pair<pair<int,int>,int>> pfsq(n+10);
int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
for(int i = 0; i < n; i++) {
int x = pts[i].fr;
int y = pts[i].sc;
minx = min(x,minx);
maxx = max(x,maxx);
miny = min(y,miny);
maxy = max(y,maxy);
pfsq[i] = sqr(minx,maxx,miny,maxy);
}
vector<pair<pair<int,int>,int>> sfsq(n+10);
minx = inf,miny=inf,maxx = -inf,maxy = -inf;
for(int i = n-1; i >= 0; i--) {
int x = pts[i].fr;
int y = pts[i].sc;
minx = min(x,minx);
maxx = max(x,maxx);
miny = min(y,miny);
maxy = max(y,maxy);
sfsq[i] = sqr(minx,maxx,miny,maxy);
}
for(int i = 0; i+1 < n; i++) {
int x0 = pfsq[i].fr.fr;
int y0 = pfsq[i].fr.sc;
int l0 = pfsq[i].sc;
int x1 = sfsq[i+1].fr.fr;
int y1 = sfsq[i+1].fr.sc;
int l1 = sfsq[i+1].sc;
bool inter = true;
if(x1 > x0+l0 or x0 > x1+l1) inter = false;
if(x1 > x0+l0 or y0 > y1+l1) inter = false;
if(inter == true) continue;
if(max(l0,l1) > ans) continue;
ansv.clear();
ansv.pb(mp(mp(x0,y0),l0));
ansv.pb(mp(mp(x1,y1),l1));
ans = max(l0,l1);
}
for(int i = 0; i < pts.size(); i++) {
swap(pts[i].fr,pts[i].sc);
}
}
{
sort(all(pts));
vector<pair<pair<int,int>,int>> pfsq(n+10);
int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
for(int i = 0; i < n; i++) {
int x = pts[i].sc;
int y = pts[i].fr;
minx = min(x,minx);
maxx = max(x,maxx);
miny = min(y,miny);
maxy = max(y,maxy);
pfsq[i] = sqr(minx,maxx,miny,maxy);
}
vector<pair<pair<int,int>,int>> sfsq(n+10);
minx = inf,miny=inf,maxx = -inf,maxy = -inf;
for(int i = n-1; i >= 0; i--) {
int x = pts[i].sc;
int y = pts[i].fr;
minx = min(x,minx);
maxx = max(x,maxx);
miny = min(y,miny);
maxy = max(y,maxy);
sfsq[i] = sqr(minx,maxx,miny,maxy);
}
for(int i = 0; i+1 < n; i++) {
int x0 = pfsq[i].fr.fr;
int y0 = pfsq[i].fr.sc;
int l0 = pfsq[i].sc;
int x1 = sfsq[i+1].fr.fr;
int y1 = sfsq[i+1].fr.sc;
int l1 = sfsq[i+1].sc;
bool inter = true;
if(x1 > x0+l0 or x0 > x1+l1) inter = false;
if(y1 > y0+l0 or y0 > y1+l1) inter = false;
if(inter == true) continue;
if(max(l0,l1) > ans) continue;
ansv.clear();
ansv.pb(mp(mp(x0,y0),l0));
ansv.pb(mp(mp(x1,y1),l1));
ans = max(l0,l1);
}
for(int i = 0; i < pts.size(); i++) {
swap(pts[i].fr,pts[i].sc);
}
}
assert(ans != inf);
for(auto x : ansv) {
cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
}
}
}
Compilation message
izvanzemaljci.cpp: In function 'int32_t main()':
izvanzemaljci.cpp:96:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < pts.size(); i++) {
| ~~^~~~~~~~~~~~
izvanzemaljci.cpp:147:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 0; i < pts.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 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 |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
50 ms |
2444 KB |
Output is correct |
| 8 |
Correct |
49 ms |
2200 KB |
Output is correct |
| 9 |
Correct |
60 ms |
2388 KB |
Output is correct |
| 10 |
Correct |
49 ms |
2328 KB |
Output is correct |
| 11 |
Correct |
49 ms |
752 KB |
Output is correct |
| # |
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 |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
