Cod sursa(job #30023)

Utilizator alextheroTandrau Alexandru alexthero Data 12 martie 2007 14:15:49
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <algorithm>

#define vmax 50005
#define nmax 50005
#define inf 1e15
#define LL double

using namespace std;

int x[nmax],y[nmax];
LL px[nmax];
int n,dx,dy,i;
LL partx = (LL)inf,party = (LL)inf;

LL mini(LL x,LL y) {
	if(x > y) return y;
	else return x;
}

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

	scanf("%d%d%d",&n,&dx,&dy);
	
	for(i = 1; i <= n; i++) 
		scanf("%d%d",&x[i],&y[i]);

	sort(x + 1,x + n + 1);
	for(i = 1; i <= n; i++) px[i] = (LL)px[i - 1] + x[i];

	int sx = 0,sy = 0;
	LL tot = 0;
	for(i = 0; i <= vmax; i++) {
		while(sy + 1 <= n && i + dx >= x[sy + 1]) sy++;
		while(sx + 1 <= n && i > x[sx + 1]) sx++;
		double i1 = (double)i;
		tot = (LL)(i1 * sx) - (LL)px[sx] + (LL)px[n] - (LL)px[sy] - (LL)(n - sy) * (LL)i1 - (LL)dx * (LL)(n -sy);
		partx = mini(partx,tot);
	}

	sort(y + 1,y + n + 1);
	for(i = 1; i <= n; i++) px[i] = (LL)px[i - 1] + y[i];
	
	sx = 0,sy = 0;
	for(i = 0; i <= vmax; i++) {
		while(sy + 1 <= n && i + dy >= y[sy + 1]) sy++;
		while(sx + 1 <= n && i > y[sx + 1]) sx++;
		double i1 = (double)i;
		tot = (LL)(i1 * sx) - px[sx] + px[n] - px[sy] - (n - sy) * i1 - dy * (n -sy);
		party = mini(party,tot);
	}

	printf("%lld\n",partx + party);
	return 0;
}