Cod sursa(job #601449)

Utilizator luckyme91wiz kid luckyme91 Data 6 iulie 2011 18:05:10
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int dist_min (vector <int> X, int Dx, vector <int> xi)
{
	int Min = 500000000, s = 0, i, j;
	for (i = 0; i <=  ((int) X.size ()) - 1 - Dx; i++)
	{
		s = 0;
		for (j = 0; j < xi.size (); j++)
		{
			if (X[xi[j]] != 0)
				if (xi[j ]< i)
					s += X[xi[j]] * (i - xi[j]);
				else
					if (i + Dx < xi[j])
						s += X[xi[j]] * (xi[j] - i - Dx);
			if (s > Min)
				break;
		}
		Min = min (s, Min);
	}
	Min = min (s, Min);
	return Min;
}
	
int main () {

ifstream in ("tribute.in");
ofstream out ("tribute.out");

int n, dx, dy, i, x, y;
in >> n >> dx >> dy;

vector <int> X (n), Y (n), xi, yi;

for (i = 0; i < n; i++)
{
	in >> x >> y;
	if (x >= X.size())
		X.resize (x + 1);
	if (y >= Y.size())
		Y.resize (y + 1);
	if (!X[x])
		xi.push_back(x);
	if (!Y[y])
		yi.push_back(y);
	X[x] ++;	
	Y[y] ++;
}
out << dist_min (X, dx, xi) + dist_min (Y, dy, yi);

return 0;
}