#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long ma=1e9,inf=1e18;
long long n,d,nn;
pair<long long,long long> a[4][100069],as[4][100069],a2[100069];
pair<pair<long long,long long>,long long> ca[3],sq[3];
bitset<100069> vtd;
int main()
{
long long i,j,ii,im,x,y,k,l,w,p,mn,mx,mn2,mx2,lh,rh,md;
bool bad;
scanf("%lld%lld",&n,&d);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
a[0][i]={x,y};
}
for(im=0;im<4;im++)
{
sort(a[im]+1,a[im]+n+1);
for(i=1;i<=n;i++)
{
as[im][i]={a[im][i].sc,i};
}
sort(as[im]+1,as[im]+n+1);
if(im<3)
{
for(i=1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
a[im+1][i]={y,-x};
}
}
}
for(lh=2,rh=2;lh<=rh;)
{
md=(lh+rh)/2;
bad=0;
for(im=0;im<4;im++)
{
if(d==1)
{
if(!im)
{
mn=inf;
mx=-inf;
mn2=inf;
mx2=-inf;
for(i=1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a[im][1].fr>md)
{
break;
}
mn2=mn;
mx2=mx;
}
if(i>n)
{
bad=1;
sq[0]={{a[im][1].fr,mn2},md};
}
}
}
else if(d==2)
{
if(im<2)
{
l=0;
for(ii=0;ii<2;ii++)
{
mn=inf;
mx=-inf;
k=l;
mn2=inf;
mx2=-inf;
for(i=l+1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a[im][l+1].fr>md)
{
break;
}
if(i==n||x!=a[im][i+1].fr)
{
k=i;
mn2=mn;
mx2=mx;
}
}
if(!ii)
{
ca[ii]={{a[im][k].fr-md,mn2},md};
}
else
{
ca[ii]={{a[im][l+1].fr,mn2},md};
}
l=k;
}
if(i>n)
{
bad=1;
for(j=0;j<d;j++)
{
sq[j]=ca[j];
}
}
}
}
else
{
mn=inf;
mx=-inf;
k=0;
mn2=inf;
mx2=-inf;
vtd.reset();
for(i=1;i<=n;i++)
{
p=as[im][i].sc;
x=a[im][p].fr;
y=a[im][p].sc;
mn=min(mn,x);
mx=max(mx,x);
if(mx-mn>md||y-as[im][1].fr>md)
{
break;
}
if(i==n||y!=as[im][i+1].fr)
{
mn2=mn;
mx2=mx;
for(;k<i;)
{
k++;
vtd[as[im][k].sc]=1;
}
}
}
ca[0]={{mn2,as[im][k].fr-md},md};
nn=0;
for(i=1;i<=n;i++)
{
if(!vtd[i])
{
nn++;
a2[nn]=a[im][i];
}
}
l=0;
for(ii=0;ii<2;ii++)
{
mn=inf;
mx=-inf;
k=l;
mn2=inf;
mx2=-inf;
for(i=l+1;i<=nn;i++)
{
x=a2[i].fr;
y=a2[i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a2[l+1].fr>md)
{
break;
}
if(i==nn||x!=a2[i+1].fr)
{
k=i;
mn2=mn;
mx2=mx;
}
}
if(!ii)
{
ca[ii+1]={{a2[k].fr-md,mn2},md};
}
else
{
ca[ii+1]={{a2[l+1].fr,mn2},md};
}
l=k;
}
if(i>nn)
{
bad=1;
for(j=0;j<d;j++)
{
sq[j]=ca[j];
}
}
if(im<2)
{
}
}
for(i=0;i<d;i++)
{
x=sq[i].fr.fr;
y=sq[i].fr.sc;
w=sq[i].sc;
sq[i].fr={y,-x-w};
}
}
if(bad)
{
rh=md-1;
}
else
{
lh=md+1;
}
}
for(i=0;i<d;i++)
{
x=sq[i].fr.fr;
y=sq[i].fr.sc;
w=sq[i].sc;
if(x<-ma*3||y<-ma*3||x>ma*3||y>ma*3)
{
x=min(max(x,-ma*3),ma*3);
y=min(max(y,-ma*3),ma*3);
w=1;
}
printf("%lld %lld %lld\n",x,y,w);
}
}
Compilation message
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:17:44: warning: variable 'mx2' set but not used [-Wunused-but-set-variable]
17 | long long i,j,ii,im,x,y,k,l,w,p,mn,mx,mn2,mx2,lh,rh,md;
| ^~~
izvanzemaljci.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%lld%lld",&n,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%lld%lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Integer 0 violates the range [1, 2*10^9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Integer 0 violates the range [1, 2*10^9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
