Cod sursa(job #554120)

Utilizator loginLogin Iustin Anca login Data 14 martie 2011 17:04:19
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
# include <fstream>
# define DIM 50005
# define INF 2000000000
using namespace std;
int n, dx, dy, x[DIM], y[DIM], st[DIM], dr[DIM], X1, X0=INF, Y1, Y0=INF;

void read ()
{
	ifstream fin ("tribute.in");
	fin>>n>>dx>>dy;
	int t;
	for(int i=1;i<=n;++i)
	{
		fin>>t;++t;
		++x[t];
		if (t<X0)X0=t;
		if (t>X1)X1=t;
		fin>>t;++t;
		++y[t];
		if (t<Y0)Y0=t;
		if (t>Y1)Y1=t;
	}
}

int f (int v[], int d, int a, int b)
{
	for(int i=1;i<=DIM-2;++i)
		st[i]=dr[i]=0;
	int i, el=0, r=INF;
	for(i=a;i<=b;++i)
	{
		st[i]=st[i-1]+el;
		el+=v[i];
	}
	el=0;
	for(int i=b;i>=a;--i)
	{
		dr[i]=dr[i+1]+el;
		el+=v[i];
	}
	for(int i=a;i+d<=b;++i)
		if (st[i]+dr[i+d]<r)
			r=st[i]+dr[i+d];
	return r;
}
	
int main ()
{
	read ();
	ofstream fout ("tribute.out");
	fout<<f(x,dx,X0,X1)+f(y,dy,Y0,Y1);
	return 0;
}