#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=1e5;
struct point{
int x, y;
};
struct compx{
bool operator()(point a, point b)const{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
};
struct compy{
bool operator()(point a, point b)const{
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
};
int k;
struct solution{
int a, b, c, d, e, f, g, h, i, j;
int longest;
solution():longest(2000000001){}
solution(int a, int b, int c):a(a), b(b), c(c){
longest=c;
}
solution(int a, int b, int c, int d, int e, int f):a(a), b(b), c(c), d(d), e(e), f(f){
longest=max(c, f);
if((a+c<=d or d+f<=a) and (b+c<=e or e+f<=b))
longest=2000000001;
}
solution(int a, int b, int c, int d, int e, int f, int g, int h, int i):a(a), b(b), c(c), d(d), e(e), f(f), g(g), h(h), i(i){
longest=max({c, f, i});
}
bool operator<(const solution& rhs)const{
return longest<rhs.longest;
}
};
int main(){
int n;
scanf("%d%d", &n, &k);
if(k==1){
int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
for(int i=n; i--;){
int x, y;
scanf("%d%d", &x, &y);
xmin=min(xmin, x);
xmax=max(xmax, x);
ymin=min(ymin, y);
ymax=max(ymax, y);
}
int s=1;
s=max(s, xmax-xmin);
s=max(s, ymax-ymin);
printf("%d %d %d\n", xmin, ymin, s);
}else if(k==2){
vector<point> points(n);
int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
for(auto& i : points){
scanf("%d%d", &i.x, &i.y);
xmin=min(xmin, i.x);
xmax=max(xmax, i.x);
ymin=min(ymin, i.y);
ymax=max(ymax, i.y);
}
// vector<int> sx, sy;
// for(auto& i : points){
// sx.push_back(i.x);
// sy.push_back(i.y);
// }
// sort(sx.begin(), sx.end());
// sort(sy.begin(), sy.end());
// multiset<int> xs, ys;
int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2.1e9, y2=2.1e9, s2=2e9;
vector<point> sortx=points, sorty=points;
sort(sortx.begin(), sortx.end(), [&](point a, point b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
});
sort(sorty.begin(), sorty.end(), [&](point a, point b){
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
});
{
set<point, compx> sx1, sx2(sortx.begin(), sortx.end());
set<point, compy> sy1, sy2(sorty.begin(), sorty.end());
while(not sx2.empty()){
sx1.insert(*sx2.begin());
sy1.insert(*sx2.begin());
sy2.erase(*sx2.begin());
sx2.erase(sx2.begin());
int cx1=sx1.rbegin()->x,
cy1=sy1.begin()->y,
cs1=max({sx1.rbegin()->x-sx1.begin()->x, sy1.rbegin()->y-sy1.begin()->y, 1});
cx1-=cs1;
int cx2=sx2.empty()?2.1e9:sx2.begin()->x,
cy2=sx2.empty()?2.1e9:sy2.begin()->y,
cs2=sx2.empty()?1:max({sx2.rbegin()->x-sx2.begin()->x, sy2.rbegin()->y-sy2.begin()->y, 1});
if((cx1+cs1<cx2 or cx2+cx2<cx1) and (cy1+cs1<cy2 or cy2+cs2<cy1))
continue;
if(max(cs1, cs2)<best){
best=max(cs1, cs2);
x1=cx1;
y1=cy1;
s1=cs1;
x2=cx2;
y2=cy2;
s2=cs2;
}
}
}
{
set<point, compx> sx1, sx2(sortx.begin(), sortx.end());
set<point, compy> sy1, sy2(sorty.begin(), sorty.end());
while(not sx2.empty()){
sx1.insert(*sy2.begin());
sy1.insert(*sy2.begin());
sx2.erase(*sy2.begin());
sy2.erase(sy2.begin());
int cx1=sx1.begin()->x,
cy1=sy1.rbegin()->y,
cs1=max({sx1.rbegin()->x-sx1.begin()->x, sy1.rbegin()->y-sy1.begin()->y, 1});
cy1-=cs1;
int cx2=sx2.empty()?2.1e9:sx2.begin()->x,
cy2=sx2.empty()?2.1e9:sy2.begin()->y,
cs2=sx2.empty()?1:max({sx2.rbegin()->x-sx2.begin()->x, sy2.rbegin()->y-sy2.begin()->y, 1});
if((cx1+cs1<cx2 or cx2+cx2<cx1) and (cy1+cs1<cy2 or cy2+cs2<cy1))
continue;
if(max(cs1, cs2)<best){
best=max(cs1, cs2);
x1=cx1;
y1=cy1;
s1=cs1;
x2=cx2;
y2=cy2;
s2=cs2;
}
}
}
printf("%d %d %d\n%d %d %d\n", x1, y1, s1, x2, y2, s2);
}else if(k==3 and n<=1000){
vector<point> points(n);
int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
for(auto& i : points){
scanf("%d%d", &i.x, &i.y);
xmin=min(xmin, i.x);
xmax=max(xmax, i.x);
ymin=min(ymin, i.y);
ymax=max(ymax, i.y);
}
vector<int> sx, sy;
for(auto& i : points){
sx.push_back(i.x);
sy.push_back(i.y);
}
sort(sx.begin(), sx.end());
sort(sy.begin(), sy.end());
multiset<int> xs, ys;
int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
}
}
Compilation message
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:167:7: warning: unused variable 'best' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~~~
izvanzemaljci.cpp:167:17: warning: unused variable 'x1' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:167:26: warning: unused variable 'y1' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:167:35: warning: unused variable 's1' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:167:43: warning: unused variable 'x2' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:167:51: warning: unused variable 'y2' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:167:59: warning: unused variable 's2' [-Wunused-variable]
167 | int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
| ^~
izvanzemaljci.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:52:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d", &i.x, &i.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:153:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%d%d", &i.x, &i.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
37 ms |
204 KB |
Output is correct |
| 8 |
Correct |
28 ms |
204 KB |
Output is correct |
| 9 |
Correct |
29 ms |
204 KB |
Output is correct |
| 10 |
Correct |
36 ms |
204 KB |
Output is correct |
| 11 |
Correct |
29 ms |
272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
