Pagini recente » Cod sursa (job #977943) | Cod sursa (job #1292461) | Cod sursa (job #2079267) | Cod sursa (job #1038263) | Cod sursa (job #519936)
Cod sursa(job #519936)
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 50010
#define ll long long
int n,dx,dy;
int x[N],y[N];
int s1[N],s2[N];
inline void citire() {
scanf("%d%d%d",&n,&dx,&dy);
for(int i=1; i<=n; ++i) {
scanf("%d%d",&x[i],&y[i]);
}
}
inline ll rezolva(int v[N],int dv) {
int i,j;
sort(v+1,v+n+1);
ll ret = 1e13,aux;
for(i=1; i<=n; ++i)
s1[i] = s1[i-1]+(ll)v[i];
for(i=n; i>0; --i)
s2[i] = s2[i+1]+(ll)v[i];
if(v[n]-v[1]<=dv)
return 0LL;
i = 0;
j = 1;
for(int t=v[1],lim=v[n]-dv+1; t<lim; ++t) {
aux = 0;
for(; v[i]<t; ++i)
;
if(i>1)
aux = (ll)t*(ll)(i-1)-s1[i-1];
for(; v[j]<=t+dv && j<=n; ++j)
;
if(j>n)
--j;
else {
if(v[j]>t+dv)
--j;
}
aux += s2[j+1]-(ll)(t+dv)*(ll)(n-j);
if(ret>aux)
ret = aux;
}
return ret;
}
int main() {
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
citire();
printf("%lld\n",rezolva(x,dx)+rezolva(y,dy));
return 0;
}