Pagini recente » Cod sursa (job #245826) | Cod sursa (job #81657) | Cod sursa (job #2487490) | Cod sursa (job #2482372) | Cod sursa (job #123033)
Cod sursa(job #123033)
#include <stdio.h>
int main()
{
int s,mino,minv,nr1,nr2,i,j,k,n,dx,dy,ss,sd;
int a[50001][2];
int absc[2][50001],ord[2][50001];
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
scanf("%d %d %d",&n,&dx,&dy);
for (i=1; i<=50000; i++)
{
absc[0][i]=0;absc[1][i]=0;
ord[0][i]=0;ord[1][i]=0;
}
absc[0][0]=0;absc[1][0]=0;
ord[0][0]=0;ord[1][0]=0;
for (i=1; i<=n; i++)
{
scanf("%d %d",&a[i][0],&a[i][1]);
absc[0][a[i][0]]=1;absc[1][a[i][0]]++;
ord[0][a[i][1]]=1;ord[1][a[i][1]]++;
}
//lucrez pe axa absciselor
k=1;nr1=0;nr2=0;s=0;
for (i=0; i<=50000; i++)
{
if (absc[0][i]==1) k=i;
if (i>dx && absc[0][i]==1)
{
nr2+=absc[1][i];
s+=absc[1][i]*(i-dx);
}
}
mino=s;
ss=0;sd=s;
for (i=dx+1; i<=k; i++)
{
if (absc[0][i]==1) nr2-=absc[1][i];
if (absc[0][i-dx-1]==1) nr1+=absc[1][i-dx-1];
sd=sd-nr2;if (nr2==0) sd=0;
ss=ss+nr1;if (nr1==0) ss=0;
s=ss+sd;
if (s<mino) mino=s;
}
//lucrez pe axa absciselor
k=1;nr1=0;nr2=0;s=0;
for (i=0; i<=50000; i++)
{
if (ord[0][i]==1) k=i;
if (i>dx && ord[0][i]==1)
{
nr2+=ord[1][i];
s+=ord[1][i]*(i-dx);
}
}
minv=s;
ss=0;sd=s;
for (i=dx+1; i<=k; i++)
{
if (ord[0][i]==1) nr2-=ord[1][i];
if (ord[0][i-dx-1]==1) nr1+=ord[1][i-dx-1];
sd=sd-nr2;if (nr2==0) sd=0;
ss=ss+nr1;if (nr1==0) ss=0;
s=ss+sd;
if (s<minv) minv=s;
}
printf("%d\n",mino+minv);
return 0;
}