Cod sursa(job #78263)

Utilizator peanutzAndrei Homorodean peanutz Data 16 august 2007 01:59:07
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <memory.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, t;
	int currentMin = 2000000000;
	int before[NMAX], after[NMAX];

    	memset(before, 0, sizeof(before));
	memset(after, 0, sizeof(after));

	for(i = x[1], j = 1, t = 0; i <= x[n]; ++i)
	{
		after[i] = after[i-1] + t;

		while(i == x[j])
			after[i] += x[j++], ++t;

        //printf("%d ", after[i]);
	}

    //printf("\n\n");

	for(i = x[n], j = n, t = 0; i >= x[1]; --i)
	{
		before[i] = before[i+1] + t;

		if(i == x[j])
			before[i] += x[j--], ++t;

        //printf("%d ", before[i]);
	}
    //printf("\n\n");

	for(i = x[1]; i < NMAX && i <= n; ++i)
	{

        	currentMin = MIN(currentMin, after[i-1] + before[i+d+1]);
	}

	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;
}