| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 743893 | jamielim | Izvanzemaljci (COI21_izvanzemaljci) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n,k;
vector<ii> all;
vector<int> find_one_square(vector<ii> v){
if(SZ(v)==0)return {0,0,1};
int minx=LLINF,maxx=-LLINF,miny=LLINF,maxy=-LLINF;
for(ii i:v){
minx=min(minx,i.fi);
maxx=max(maxx,i.fi);
miny=min(miny,i.se);
maxy=max(maxy,i.se);
}
int l=max(1,max(maxx-minx,maxy-miny));
return {minx,miny,l};
}
int32_t main(){
scanf("%lld%lld",&n,&k);
int x,y;
for(int i=0;i<n;i++){
scanf("%lld%lld",&x,&y);
all.pb(x,y);
}
if(k==1){
vector<int> ans=find_one_square(all);
printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
}else if(k==2){
int minx=LLINF,maxx=-LLINF,miny=LLINF,maxy=-LLINF;
for(ii i:all){
minx=min(minx,i.fi);
maxx=max(maxx,i.fi);
miny=min(miny,i.se);
maxy=max(maxy,i.se);
}
int le=1,ri=3*INF;
while(le<ri){
int mi=(le+ri)/2;
int ny=LLINF,xy=-LLINF;
for(ii i:all){
if(i.fi<=minx+mi){
ny=min(ny,i.se);
xy=max(xy,i.se);
}
}
vector<ii> v1,v2;
for(ii i:all){
if(i.fi>minx+mi||i.se>ny+mi)v1.pb(i);
if(i.fi>minx+mi||i.se<xy-mi)v2.pb(i);
}
vector<int> res1=find_one_square(v1);
vector<int> res2=find_one_square(v2);
if(res1[2]<=mi||res2[2]<=mi)ri=mi;
else le=mi+1;
}
int ny=LLINF,xy=-LLINF;
for(ii i:all){
if(i.fi<=minx+le){
ny=min(ny,i.se);
xy=max(xy,i.se);
}
}
vector<ii> v1,v2;
for(ii i:all){
if(i.fi>minx+le||i.se>ny+le)v1.pb(i);
if(i.fi>minx+le||i.se<xy-le)v2.pb(i);
}
vector<int> res1=find_one_square(v1);
vector<int> res2=find_one_square(v2);
if(res1[2]<=le){
printf("%lld %lld %lld\n",res1[0],res1[1],res1[2]);
printf("%lld %lld %lld\n",minx,ny,le);
}else{
printf("%lld %lld %lld\n",res2[0],res2[1],res2[2]);
printf("%lld %lld %lld\n",minx,xy-le,le);
}
}else{
}
}