Cod sursa(job #810108)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 9 noiembrie 2012 18:00:42
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

#define maxdim 50005
#define pb push_back
#define mp make_pair

using namespace std;

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

int n,x0,y0;
int list[maxdim];
vector< pair<int,int> >A[4];

inline void rotate1 () {

	for ( int i = 0 ; i < A[1].size() ; ++i ){
		A[1][i].second = -A[1][i].second;
	}
}

inline void rotate2 () {

	for ( int i = 0 ; i < A[2].size() ; ++i ){
		A[2][i].first = -A[2][i].first;
		A[2][i].second = -A[2][i].second;
	}
}

inline void rotate3 () {

	for ( int i = 0 ; i < A[3].size() ; ++i ){
		A[3][i].first = -A[3][i].first;
	}
}

inline int solve ( vector< pair<int,int> >&V ){

	sort(V.begin(),V.end());
	list[0] = 0;
	for ( int i = 0 ; i < V.size() ; ++i ){
		int y = V[i].second;
		
		int left = 1,right = list[0];
		while ( left <= right ){
			int middle = (left + right)>>1;
			
			if ( list[middle] < y ){
				right = middle-1;
			}
			else{
				left = middle+1;
			}
		}
		
		if ( left == list[0]+1 ){
			list[++list[0]] = y;
		}
		else{
			list[left] = y;
		}
	}
	
	return list[0];
}

int main () {
	
	fscanf(f,"%d %d %d",&n,&x0,&y0);
	int xnow,ynow;
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&xnow,&ynow);
		xnow -= x0; ynow -= y0;
		if ( xnow > 0 && ynow > 0 )	A[0].pb(mp(xnow,ynow));
		if ( xnow > 0 && ynow < 0 )	A[1].pb(mp(xnow,ynow));
		if ( xnow < 0 && ynow < 0 )	A[2].pb(mp(xnow,ynow));
		if ( xnow < 0 && ynow > 0 )	A[3].pb(mp(xnow,ynow));
	}
	
	rotate1(); rotate2(); rotate3();
	
	int sol = solve(A[0]) + solve(A[1]) + solve(A[2]) + solve(A[3]);
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}