Cod sursa(job #78266)

Utilizator peanutzAndrei Homorodean peanutz Data 16 august 2007 02:36:35
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

#define NMAX 390010

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)
//#define umm(

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]+20000; ++i)
	{
		after[i] =  ((i > 0) ? (after[i-1]) : 0) + t;

		while(j <= n && i == x[j])
			j++, ++t;

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

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

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

		while(j <= n && i == x[j])
			j--, ++t;

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

	for(i = 0; i <= x[n]+20000; ++i)
	{

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

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