Cod sursa(job #672286)

Utilizator alutzuAlexandru Stoica alutzu Data 1 februarie 2012 20:29:54
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>

int fx[50005], fy[50005], X[50005], Y[50005] ;

struct PUNCT {
	int x , y ;
};

PUNCT punct[50005];

int main ( )
{
	
	freopen ( "tribute.in", "r", stdin ) ;
	freopen ( "tribute.out", "w", stdout ) ;
	
	int N , DX , DY , S = 0 ;
	int min = 50005, mini ;
	int minn = 50005 , minni ;
	int i ;
	
	scanf ( "%d%d%d", & N , & DX , & DY ) ;
	
	for ( i = 1 ; i <= N ; ++ i )
	{
		scanf ( "%d%d" , &punct[i].x ,&punct[i].y ) ;
		//printf ( "(%d,%d)" , punct[i].x , punct[i].y ) ;
		++ fx [ punct[i].x ] ;
		//printf ( "FX[%d]:%d\n", punct[i].x , fx[punct[i].x] ) ;
		++ fy [ punct[i].y ] ;
	}

	X[0] = fx[0] ;
	Y[0] = fy[0] ;
	
	for ( i = 1 ; i <= 50000 ; ++ i ) 
	{
		X [i] = X[i-1] + fx[i] ;
		Y [i] = Y[i-1] + fy[i] ;
	}
	
	for ( i = 0+DX ; i <= 50000 ; ++ i )
	{
		//printf ( "**(%d)\n" , fx[i] ) ;
		if ( fx[i] )
		{
			//printf ( "( %d , %d ) \n" , fx[i] , i-DX ) ;
			S += fx[i]*(i-DX) ;
		}
	}
	
	for ( i = 1 ; i <= 50000-DX ; ++ i )
	{
		//verificam marginea din stanga aka toate elementele de pe margine si care cresc cu 1
		
		//printf ( "X[%d]:%d ** X[50000]:%d ** X[%d]:%d" , i , X[i] , X[50000] , i+DX , X[i+DX] ) ;
		S += X[i-1] - ( X[50000] - X[i+DX-1] ) ;
		if ( S < min )
		{
			min = S ;
			mini = i ;
		}
		//printf ( "(i:%d,S:%d)\n" , i , S ) ;
	}
	S = 0 ;
	for ( i = 0+DY ; i <= 50000 ; ++ i )
	{
		//printf ( "**(%d)\n" , fx[i] ) ;
		if ( fy[i] )
		{
			//printf ( "( %d , %d ) \n" , fy[i] , i ) ;
			S += fy[i]*(i-DY) ;
		}
	}
	
	//printf ( "%d\n", S ) ;
	
	for ( i = 1 ; i <= 5-DY ; ++ i )
	{
		//verificam marginea din stanga aka toate elementele de pe margine si care cresc cu 1
		
		//printf ( "Y[%d]:%d ** Y[50000]:%d ** Y[%d]:%d" , i , Y[i] , Y[50000] , i+DY , Y[i+DY] ) ;
		S += Y[i-1] - ( Y[50000] - Y[i+DY-1] ) ;
		if ( S < minn )
		{
			minn = S ;
			minni = i ;
		}
		//printf ( "(i:%d,S:%d)\n" , i , S ) ;
	}
	
	
	printf ( "%d" , min + minn ) ;
	
	
	return 0 ;
}