Cod sursa(job #387464)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 27 ianuarie 2010 18:45:48
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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 p,u,i,j,d,dist_min,xx,yy;

	d=0;
	xx=v[0];
	yy=v[0]+l;
	
	//calculeaza cea mai mare pozitie dupa j
	i=1;
	while (v[i]<yy)
		i++;

	//dif de la i pana la n-1
	for (j=i;j<n;++j) 
		d+=(v[j]-yy);
	dist_min=d;
	p=1;
	u=i;
	while (u<n)
	{
		if (v[p]-xx<v[u]-yy)
		{
			d=d+p*(v[p]-xx)-(n-u)*(v[p]-xx);
			xx=v[p];
			yy=xx+l;
			p++; 
		}
		else
		{
			d=d+p*(v[u]-yy)-(n-u)*(v[u]-yy);
			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);
	x[n]=0x3f3f3f3f;
	y[n]=0x3f3f3f3f;
	
	sol+=dist(x,dx);
	sol+=dist(y,dy);
	
	printf("%d", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}