Cod sursa(job #387448)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 27 ianuarie 2010 18:20:52
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=2;
	xx=v[1];
	yy=v[1]+l;
	int d=0;
	//cauta cea mai mare valoare dupa yy
	i=2;
	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]-v[u]<xx-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=1;i<=n;++i)
		 scanf("%d %d", &x[i], &y[i]);
	
	sort(x+1,x+n+1);
	sort(y+1,y+n+1);
	
	sol+=dist(x,dx);
	sol+=dist(y,dy);
	
	printf("%d", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}