Cod sursa(job #181820)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 19 aprilie 2008 00:18:56
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <algorithm>
#define INF 100000
#define NMAX 50666

using namespace std;

int X[NMAX], Y[NMAX], N;

int dist(int v[NMAX], int l, int &p)
{
	int cs = 0, cd, d = 0, i = 1, a, b, j, dmin;

	a = v[cs];
	b = v[cs]+l;
	while (v[i] < b) i++;

	for (j = i; j < N; j++) d += (v[j]-b);
	dmin = d;
	p = a;

	cs = 1;
	cd = i;

	while (cd < N)
	{
			if (v[cs]-a < v[cd]-b)
			{
					d = d+cs*(v[cs]-a)-(N-cd)*(v[cs]-a);
					a = v[cs];
					b = a+l;
					cs++; 
			}
			else
			{
					d = d+cs*(v[cd]-b)-(N-cd)*(v[cd]-b);
					b = v[cd];
					a = b-l;
					cd++;
			}
			if (dmin > d) dmin = d, p = a;
	}

	return dmin;

}

int main()
{
	int i, l, c, s = 0, lx, ly;

	freopen("tribute.in", "r", stdin);
	scanf("%d %d %d", &N, &lx, &ly);

	for(i = 0; i < N; i++) scanf("%d %d", X+i, Y+i);
	sort(&X[0], &X[N]); X[N] = INF;
	sort(&Y[0], &Y[N]); Y[N] = INF;

	s+=dist(X, lx, l);
	s+=dist(Y, ly, c);

	freopen("tribute.out", "w", stdout);
	printf("%d\n", s);

	return 0;

}