Cod sursa(job #73657)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 20 iulie 2007 10:17:43
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define fin  "tribute.in"
#define fout "tribute.out"
#define Nmax 50001
#define MAX  1<<30

#define DBGg
#define FL

struct dot { int x,y; };

vector <dot> v;
int N,dx,dy,a[Nmax],b[Nmax];
int x1,y1,x2,y2;
int ret;

bool cmpx(dot a,dot b)
{	
	return a.x < b.x;
}

bool cmpy(dot a,dot b)
{
	return a.y < b.y;
}

int main()
{
	int i,j,bst;
	dot aux;

	freopen(fin,"r",stdin);
#ifdef FL
	freopen(fout,"w",stdout);
#endif 
	scanf("%d%d%d",&N,&dx,&dy);

	for (i=0;i<N;++i)
	{
		scanf("%d%d",&aux.x,&aux.y);
		v.push_back(aux);
	}
	
//baleiez pe OX
	sort(v.begin(),v.end(),cmpx);
	
	for (i=1;i<N;++i)
	{
		a[v[i].x]=a[v[i-1].x]+i*(v[i].x-v[i-1].x);
		
		for (j=v[i-1].x+1;j<v[i].x;++j)
			a[j]=a[v[i-1].x]+i*(j-v[i-1].x);
	}
	for (i=N-2;i>=0;--i)
	{
		b[v[i].x]=b[v[i+1].x]+(N-i-1)*(v[i+1].x-v[i].x);
		for (j=v[i+1].x-1;j>v[i].x;--j)
			b[j]=b[v[i+1].x]+(N-i-1)*(v[i+1].x-j);
	}
	bst=MAX;
	for (i=v[0].x;i<=v[N-1].x;++i)
		if (a[i]+b[i+dx] < bst)
		{
			bst=a[i]+b[i+dx];
			x1=i;
		}
#ifdef DBG
	for (i=v[0].x;i<=v[N-1].x;++i)
		printf("%d ",a[i]);
	printf("\n");
	for (i=v[0].x;i<=v[N-1].x;++i)
		printf("%d ",b[i]);
	printf("\n\n");
#endif

//gata

//baleiez pe OY

	sort(v.begin(),v.end(),cmpy);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));

	for (i=1;i<N;++i)
	{
		a[v[i].y]=a[v[i-1].y]+i*(v[i].y-v[i-1].y);
		
		for (j=v[i-1].y+1;j<v[i].y;++j)
			a[j]=a[v[i-1].y]+i*(j-v[i-1].y);
	}
	for (i=N-2;i>=0;--i)
	{
		b[v[i].y]=b[v[i+1].y]+(N-i-1)*(v[i+1].y-v[i].y);
		
		for (j=v[i+1].y-1;j>v[i].y;--j)
			b[j]=b[v[i+1].y]+(N-i-1)*(v[i+1].y-j);
	}
	bst=MAX;
	for (i=v[0].y;i<=v[N-1].y;++i)
		if (a[i]+b[i+dy] < bst)
		{
			bst=a[i]+b[i+dy];
			y1=i;
		}
#ifdef DBG
	for (i=v[0].x;i<=v[N-1].x;++i)
		printf("%d ",a[i]);
	printf("\n");
	for (i=v[0].x;i<=v[N-1].x;++i)
		printf("%d ",b[i]);
	printf("\n\n");
#endif

//gata , am coordonata coltului stang jos in x si y
	
#ifdef DBG
	printf("%d %d\n",x1,y1);
#endif
	//okay , sa computez distanta totala

	x2=x1+dx; y2=y1+dy;
	int cx,cy;

	for (i=0;i<N;++i)
	{	
		if ( v[i].x < x1 || x2 < v[i].x ) 
			if (v[i].x > x2) 
				cx=v[i].x-x2;
			else
				cx=x1-v[i].x;
		else
			cx=0;
		if ( v[i].y < y1 || y2 < v[i].y ) 
			if (v[i].y > y2) 
				cy=v[i].y-y2;
			else
				cy=y1-v[i].y;
		else
			cy=0;
		ret+=cx+cy;
	}
	
	printf("%d\n",ret);

	return 0;
}