Cod sursa(job #33797)

Utilizator damaDamaschin Mihai dama Data 19 martie 2007 20:26:02
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <algorithm>

//using namespace std;
using std::sort;


struct point
{
	int x, y;
};

int n, dx, dy, sumx, sumy, min, sol;
point a[50001];

bool cmpx(point one, point two)
{
	return one.x < two.x || (one.x == two.x && one.y < two.y);
}

bool cmpy(point one, point two)
{
	return one.y < two.y || (one.y == two.y && one.x < two.y);
}

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


	int  i, cnt1, cnt2, sx = 0, sy = 0;
	scanf("%d%d%d", &n, &dx, &dy);

	for(i = 1; i <= n; ++i)
	{
		scanf("%d %d", &a[i].x, &a[i].y);
		if(a[i].x >= dx)
			sumx += a[i].x - dx;
		if(a[i].y >= dy)
			sumy += a[i].y - dy;
	}
//	printf("%d %d\n", sumx, sumy);
	sort(a + 1, a + n + 1, cmpx);

	min = sumx;
	cnt1 = 1;
	cnt2 = 1;
	
	for(i = 1; i <= 50000; ++i)
	{
		while(i > a[cnt1].x && cnt1 <= n)
			++cnt1;
		while(i + dx > a[cnt2].x && cnt2 <= n)
			++cnt2;
		sumx += cnt1 - 1;
		sumx -= (n - cnt2 + 1);
		if(sumx < min)
		{
			min = sumx;
			sx = i;
		}
	}
	sol = min;

	sort(a + 1, a + n + 1, cmpy);

	min = sumy;
	cnt1 = 1;
	cnt2 = 1;

//	printf("%d", min);
	for(i = 1; i <= 50000; ++i)
	{
		while(i > a[cnt1].y && cnt1 <= n)
			++cnt1;
		while(i + dy > a[cnt2].y && cnt2 <= n)
			++cnt2;
		sumy += cnt1 - 1;
		sumy -= (n - cnt2 + 1);
		if(sumy < min)
		{
			min = sumy;
			sy = i;
		}
	}

//	printf("%d", min);
	sol += min;

	printf("%d\n", sol);
//	printf("%d %d", sx, sy);
	return 0;
}