Cod sursa(job #701824)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 1 martie 2012 18:00:31
Problema Tribute Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<cstdio>
#include<algorithm>
using namespace std;

int n,dx,dy,i,x,y,cx[50010],cy[50010],dl[50010],dr[50010],cont,solp,solx,soly,inf=1<<30;

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	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,&y);
		cx[x]++;
		cy[y]++;
	}
}

void solve()
{
	cont=0;
	for(i=1;i<=50000;i++)
	{
		cont+=cx[i-1];
		dl[i]=dl[i-1]+cont;
	}
	cont=0;
	for(i=49999;i>=0;i--)
	{
		cont+=cx[i+1];
		dr[i]=dr[i+1]+cont;
	}
	solx=inf;
	for(i=0;i<=50000;i++)
	{
		solp=dl[i]+dr[i+dx];
		solx=min(solx,solp);
	}
		cont=0;
	for(i=1;i<=50000;i++)
	{
		cont+=cy[i-1];
		dl[i]=dl[i-1]+cont;
	}
	cont=0;
	for(i=49999;i>=0;i--)
	{
		cont+=cy[i+1];
		dr[i]=dr[i+1]+cont;
	}
	soly=inf;
	for(i=0;i<=50000;i++)
	{
		solp=dl[i]+dr[i+dy];
		soly=min(soly,solp);
	}
	printf("%d\n",solx+soly);
}