#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=1e5;
struct point{
int x, y;
};
int k;
struct solution{
int a, b, c, d, e, f, g, h, i, j;
long long area;
solution():area(4000000000000000003){}
solution(int a, int b, int c):a(a), b(b), c(c){
area=(long long)c*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){
area=(long long)c*c+(long long)f*f;
if((a+c<=d or d+f<=a) and (b+c<=e or e+f<=b))
area=4000000000000000003;
}
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){
area=(long long)c*c+(long long)f*f+(long long)i*i;
}
bool operator<(const solution& rhs)const{
return area<rhs.area;
}
};
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){
solution ans;
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;
//lower left exists
{
xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
vector<point> capture1=points;
sort(capture1.begin(), capture1.end(), [&](point a, point b){
return max(a.x-xmin, a.y-ymin)<max(b.x-xmin, b.y-ymin);
});
for(auto i : capture1){
xs.erase(xs.lower_bound(i.x));
ys.erase(ys.lower_bound(i.y));
int x1=xmin, y1=ymin, s1=max({i.x-xmin, i.y-ymin, 1});
int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
}
}
//upper left exists
{
xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
vector<point> capture1=points;
sort(capture1.begin(), capture1.end(), [&](point a, point b){
return max(a.x-xmin, ymax-a.y)<max(b.x-xmin, ymax-b.y);
});
for(auto i : capture1){
xs.erase(xs.lower_bound(i.x));
ys.erase(ys.lower_bound(i.y));
int x1=xmin, y1=ymax, s1=max({i.x-xmin, ymax-i.y, 1});
y1-=s1;
int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
}
}
//lower right exists
{
xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
vector<point> capture1=points;
sort(capture1.begin(), capture1.end(), [&](point a, point b){
return max(xmax-a.x, a.y-ymin)<max(xmax-b.x, b.y-ymin);
});
for(auto i : capture1){
xs.erase(xs.lower_bound(i.x));
ys.erase(ys.lower_bound(i.y));
int x1=xmax, y1=ymin, s1=max({xmax-i.x, i.y-ymin, 1});
x1-=s1;
int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
}
}
printf("%d %d %d\n%d %d %d\n", ans.a, ans.b, ans.c, ans.d, ans.e, ans.f);
}else if(k==3 and n<=1000){
}
}
Compilation message
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d%d", &i.x, &i.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
28 ms |
276 KB |
Output is correct |
| 8 |
Correct |
29 ms |
204 KB |
Output is correct |
| 9 |
Correct |
29 ms |
264 KB |
Output is correct |
| 10 |
Correct |
29 ms |
268 KB |
Output is correct |
| 11 |
Correct |
28 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 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 |
0 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
