Pagini recente » Cod sursa (job #3164542) | Cod sursa (job #309590) | Cod sursa (job #250608) | Cod sursa (job #477017)
Cod sursa(job #477017)
/* 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;
}