Pagini recente » Cod sursa (job #613015) | Cod sursa (job #67277) | Cod sursa (job #2982765) | Cod sursa (job #888712) | Cod sursa (job #1657923)
#include <cstdio>
#include <algorithm>
#define MAXN 50000
using namespace std;
int x[MAXN],y[MAXN],x1[MAXN],y1[MAXN],ssm1[MAXN+1],ssm2[MAXN+1],vfx[MAXN+1],vfy[MAXN+1];
int n;
inline int myabs(int x){
if(x<0) return -x;
return x;
}
inline int getmin(int a,int b){
if(a>b) return b;
return a;
}
inline int cauta(int st,int dr,int *v){
int s=0;
for(int i=0;i<n;i++)
if(st>v[i]||v[i]>dr)
s=s+getmin(myabs(v[i]-st),myabs(v[i]-dr));
return s;
}
int main(){
FILE*fi,*fout;
int dx,dy,i,minx,miny,xm,ym,s;
fi=fopen("tribute.in" ,"r");
fout=fopen("tribute.out" ,"w");
fscanf(fi,"%d%d%d" ,&n,&dx,&dy);
for(i=0;i<n;i++){
fscanf(fi,"%d%d" ,&x[i],&y[i]);
x1[i]=x[i];
y1[i]=y[i];
vfx[x[i]]++;
vfy[y[i]]++;
}
sort(x1,x1+n);
sort(y1,y1+n);
xm=x1[(n-1)/2];
ym=y1[(n-1)/2];
for(i=0;i<=MAXN;i++)
if(i==0)
ssm1[i]=vfx[i];
else
ssm1[i]=ssm1[i-1]+vfx[i];
for(i=MAXN;i>=0;i--)
if(i==MAXN)
ssm2[i]=vfx[i];
else
ssm2[i]=ssm2[i+1]+vfx[i];
minx=s=cauta(0,dx,x);
for(i=dx+1;i<=xm+dx;i++){
s=s+ssm1[i-dx-1]-ssm2[i];
if(minx>s)
minx=s;
}
for(i=0;i<=MAXN;i++)
if(i==0)
ssm1[i]=vfy[i];
else
ssm1[i]=ssm1[i-1]+vfy[i];
for(i=MAXN;i>=0;i--)
if(i==MAXN)
ssm2[i]=vfy[i];
else
ssm2[i]=ssm2[i+1]+vfy[i];
miny=s=cauta(0,dy,y);
for(i=dy+1;i<=ym+dy;i++){
s=s+ssm1[i-dy-1]-ssm2[i];
if(miny>s)
miny=s;
}
fprintf(fout,"%d" ,minx+miny);
fclose(fi);
fclose(fout);
return 0;
}