Cod sursa(job #387459)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 27 ianuarie 2010 18:39:18
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "tribute.in"
#define file_out "tribute.out"

#define Nmax 50101

int x[Nmax];
int y[Nmax];
int n,dx,dy,sol;

int dist(int v[Nmax], int l)
{
	int i,j;
	int p,u,xx,yy,dist_min=0;
	p=1;
	xx=v[0];
	yy=v[0]+l;
	int d=0;
	//cauta cea mai mare valoare dupa yy
	i=1;
	while (v[i]<yy)
		   i++;
	//calculeaza de la i pana la n dif
	for (j=i;j<=n;++j)
		 d+=(v[j]-yy);
	dist_min=d;
	
	u=i;
	
	while(u<n)
	{
		if (v[p]-xx<v[u]-yy)
		{
			d+=(v[p]-xx)*p-(v[p]-xx)*(n-u);
			xx=v[p];
			yy=xx+l;
			p++;
		}
		else
		{
			d+=(v[u]-yy)*p-(v[u]-yy)*(n-u);
			yy=v[u];
			xx=yy-l;
			u++;
		}
		if (dist_min>d) 
			dist_min=d;
	}
	
	return dist_min;
}
	
	


int main()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n, &dx, &dy);

	for (i=0;i<n;++i)
		 scanf("%d %d", &x[i], &y[i]);
	
	sort(x,x+n);
	sort(y,y+n);
	

	
	sol+=dist(x,dx);
	sol+=dist(y,dy);
	
	printf("%d", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}