Cod sursa(job #123037)

Utilizator savimSerban Andrei Stan savim Data 14 ianuarie 2008 13:16:22
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#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 ordonatelor
	k=1;nr1=0;nr2=0;s=0;
	for (i=0; i<=50000; i++)
	{
		if (ord[0][i]==1) k=i;
		if (i>dy && ord[0][i]==1)
		{
			nr2+=ord[1][i];
			s+=ord[1][i]*(i-dy);
		}
	}

	minv=s;
	ss=0;sd=s;
	for (i=dy+1; i<=k; i++)
	{
		if (ord[0][i]==1) nr2-=ord[1][i];
		if (ord[0][i-dy-1]==1) nr1+=ord[1][i-dy-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;
}