Cod sursa(job #78251)

Utilizator peanutzAndrei Homorodean peanutz Data 15 august 2007 23:29:44
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX 50005

int x[NMAX], y[NMAX];
int n, dx, dy;
int minx, miny;

void read()
{
	int i;
	scanf("%d%d%d", &n, &dx, &dy);
	for(i = 1; i <= n; ++i)
		scanf("%d%d", x+i, y+i);
}

#define MIN(a, b) ((a) < (b)) ? (a) : (b)
#define ABS(a) ((a) > 0) ? (a) : -(a)

int solve(int x[NMAX], int d)
{
	int i, j;
	int first, last, lastlast, t;
	int currentMin = 2000000000;
	int before, after;

	last = 1;
	before = after = 0;
	
	while(last < n && x[last+1] <= x[1] + d)
		++last;
	
	for(i = last+1; i <= n; ++i)
		before += x[i]-x[last];

    first = 1;
	for(i = x[1]; i <= 50005 && i <= n; ++i)
	{
       t = 0;
       for(j = 1; x[j] < i && j <= n; ++j)
             t += i-x[j];

       for(; i <= x[j] && i+d >= x[j]; ++j);

       for(; j <= n; ++j)
             t += x[j] - i - d;


        currentMin = MIN(currentMin, t);
        //printf("%d %d %d %d\n", first, last, i, currentMin);
	}
        //printf("\n\n\n");

        return currentMin;
}	

int main()
{
	freopen("tribute.in", "r", stdin);
	freopen("tribute.out", "w", stdout);

	read();
	
	sort(x+1, x+n+1);
	sort(y+1, y+n+1);

	minx = solve(x, dx);
	miny = solve(y, dy);
	
	printf("%d\n", minx+miny);	

	return 0;
}