Cod sursa(job #486828)

Utilizator ConsstantinTabacu Raul Consstantin Data 22 septembrie 2010 20:43:45
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<algorithm>
#define Minn(a , b ) a>b?b:a
using namespace std;

int vx[ 50010 ],vy[ 50010 ],ss[ 50010 ],sd[ 50010 ],n,Dx,Dy,X,Y,i,j,k,Sol,t,Min;

int Bs(int v[],int val){
int p,u,m,sol = 0;
p = 1;
u = n;
while(p <= u)
	{m = (p + u)>>1;
	if(v[ m ] >= val)
		sol = m;
	
	if(v[ m ] > val)
		u = m-1;
	else
		p = m + 1;
	}
return sol;

}
int Bs1(int v[],int val){

int p,u,m,sol = 0;
p = 1 ; u = n;
while(p <= u )
	{m = (p+ u )>>1;
	if(v[ m ] <= val)
		sol = m;
	if(v[ m ] < val)
		p = m+1;
	else
		u = m-1;
	}
return sol;

}
int main(){
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);
	vx[i] = X;
	vy[i] = Y;
	}
	
sort(vx+1,vx+1+n);
sort(vy+1,vy+1+n);

for(i = 2 ; i <= n; i++)
	ss[ i ] = ss[i - 1] + (vx[ i ] - vx[ i - 1 ]) * (i-1);
for(j = n-1; i >= 1 ; i--)
	sd[ i ] = sd[ i + 1 ] + (vx[ i + 1 ] - vx[ i ] )*(n-i);
Min = 1<<30;

for(i = 1 ; i <= n ; i++)
	{k = Bs(vx,vx[ i ] + Dx);
	if(k){
		t = ss[ i ] + sd[ k ] + (n - k +1) * ( vx[ k ] - vx[ i ] - Dx);
		Min = Minn(Min,t);}
	}
for(i = n; i >=1 ; --i)
	{k = Bs1(vx,vx[i] - Dx);
	if(k)
		{t = sd[i] + ss[k] + k  * (vx[ i ] - vx[k] - Dx);
		Min = Minn(Min,t);
		}
	}
if(Min != (1<<30))
Sol += Min;


for(i = 2 ; i <= n; i++)
	ss[ i ] = ss[i - 1] + (vy[ i ] - vy[ i - 1 ]) * (i-1);
for(j = n-1; i >= 1 ; i--)
	sd[ i ] = sd[ i + 1 ] + (vy[ i + 1 ] - vy[ i ] )*(n-i);
Min = 1<<30;

for(i = 1 ; i <= n ; i++)
	{k = Bs(vy,vy[ i ] + Dy);
	if(k){
		t = ss[ i ] + sd[ k ] + (n - k +1) * ( vy[ k ] - vy[ i ] - Dy);
		Min = Minn(Min,t);}
	
	}
for(i = n; i >=1 ; --i)
	{k = Bs1(vy,vy[i] - Dy);
	if(k)
		{t = sd[i] + ss[k] + k  * (vy[ i ] - vy[k] - Dy);
		Min = Minn(Min,t);
		}
	}
if(Min != (1<<30))
Sol += Min;

printf("%d",Sol);

return 0;}