Cod sursa(job #645440)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 9 decembrie 2011 17:12:29
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<algorithm>

#define maxn 50005
#define INF (1<<30)

using namespace std;

FILE*f=fopen("tribute.in","r");
FILE*g=fopen("tribute.out","w");

const int maxdim  = 50001;
int n,dx,dy,s,i;
int x[maxn],y[maxn],c_st[maxn],c_dr[maxn];

int dist ( int v[] , int d ){
	sort(v+1,v+n+1);
	
	int p;
	for ( p = 0 , i = 1 ; i <= maxdim ; ++i ){
		c_st[i] = c_st[i-1];
		while ( v[p+1] == i ){
			++p; --c_st[i];
		}
		c_st[i] += p;
	}
	for ( p = n + 1 , i = maxdim ; i >= 1 ; --i ){
		c_dr[i] = c_dr[i+1];
		while ( v[p-1] == i ){
			--p; --c_dr[i];
		}
		c_dr[i] += n - p + 1;
	}
	
	int best = INF;
	
	for ( i = 1 ; i + d - 1 <= maxdim ; ++i ){
		if ( c_st[i] + c_dr[i+d] < best ){
			best = c_st[i] + c_dr[i+d];
		}
	}
	
	return best;
}

int main () {
	
	fscanf(f,"%d %d %d",&n,&dx,&dy);
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&x[i],&y[i]); ++x[i]; ++y[i];
	}
	
	s = dist(x,dx) + dist(y,dy);
	
	fprintf(g,"%d\n",s);
	
	fclose(f);
	fclose(g);
	
	return 0;
}