Cod sursa(job #1017752)

Utilizator tuzi92Tuzes-Katai Tamas tuzi92 Data 28 octombrie 2013 11:27:49
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <cstdlib>

#define fr(i, a, b) for(int i=a; i<b; ++i)
#define INF 2147483647;

int n, dx, dy;
int x[500000];
int y[500000];
int minx, miny;
int maxx = 0, maxy = 0;
int ddx, ddy, hatar, min, max, k, km1, dxmk, dymk, dxmkm1, dymkm1;

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

	scanf("%d%d%d", &n, &dx, &dy);
	fr(i, 0, n)
	{ 
		scanf("%d%d", &x[i], &y[i]); 
		if (x[i]<minx) minx = x[i]; 
		if (x[i]>maxx) maxx = x[i]; 
		if (y[i]<miny) miny = y[i]; 
		if (y[i]>maxy) maxy = y[i]; 
	}

	min = minx; max = maxx-dx;
	while(min!=max)
	{
		maxx = 0;
		float a = (float)(min+max)/2+0.5;
		k = (int)a;
		km1 = k-1;
		dxmk = dx+k;
		fr(j, 0, n)
		{
			if (x[j]<k) maxx += k-x[j];
			else if (x[j]>k+dx) maxx += x[j]-dxmk;
		}
		minx = 0;
		dxmkm1 = dx+km1;
		fr(j, 0, n)
		{
			if (x[j]<km1) minx += km1-x[j];
			else if (x[j]>km1+dx) minx += x[j]-dxmkm1;
		}
		if (minx<maxx) max = km1;
		else min = k;
	}
	if (minx>maxx) minx = maxx;
	
	min = miny; max = maxy-dy;
	while(min!=max)
	{
		maxy = 0;
		float a = (float)(min+max)/2+0.5;
		k = (int)a;
		km1 = k-1;
		dymk = dy+k;
		fr(j, 0, n)
		{
			if (y[j]<k) maxy += k-y[j];
			else if (y[j]>k+dy) maxy += y[j]-dymk;
		}
		miny = 0;
		dymkm1 = dy+km1;
		fr(j, 0, n)
		{
			if (y[j]<km1) miny += km1-y[j];
			else if (y[j]>km1+dy) miny += y[j]-dymkm1;
		}
		if (miny<maxy) max = km1;
		else min = k;
	}
	if (miny>maxy) miny = maxy;

	printf("%d", minx+miny);
	return 0;
}