Cod sursa(job #477017)

Utilizator marius135Dumitran Adrian Marius marius135 Data 13 august 2010 00:17:36
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
/* se descompune pe fiecare cordonata in parte
si apoi se alege o pozitie centrala
*/

#include<stdio.h>
#define maxn 64 * 1024

int X[ maxn ], Y[ maxn ];
unsigned int CostX[ maxn ], CostY[ maxn ];

int main()
{
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	int N, DX, DY;
	scanf("%d %d %d", &N, &DX, &DY);
	
	for( int i = 1; i <= N; ++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		X[ a ]++;
		Y[ b ]++;
	}
	
	
	unsigned int cost1 = 1000000000, cost2 = 1000000000;
	cost1 *= 4; cost2 *=4;
	int nrX = X[ 0 ], nrY = Y[ 0 ];
	for( int i = 1 ; i<= 50000; ++i)
	{
		CostX[ i ] = CostX[ i - 1 ] + nrX; nrX += X[ i ];
		CostY[ i ] = CostY[ i - 1 ] + nrY; nrY += Y[ i ];
	}
	nrX = X[ 50000 ], nrY = Y[ 50000 ];
	unsigned int	cX = 0, cY = 0;
	for( int i = 50000; i >= 0; --i)
	{
		cX += nrX; nrX += X[ i ];
		cY += nrY; nrY += Y[ i ];
		if( i >= DX)
			if( cX + CostX[ i - DX ] < cost1 ) 
				cost1 = cX + CostX[ i - DX ];
		if( i >= DY)
			if( cY + CostY[ i - DY ] < cost2 ) 
				cost2 = cY + CostY[ i - DY ];
		
	}
	printf("%d\n", cost1 + cost2);
	return 0;
}