Cod sursa(job #483640)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 9 septembrie 2010 15:38:10
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define Nmax 50002
#define x first
#define y second
#define INF 2147000000

using namespace std;

vector< pair<int,int> > V[5];
int S[Nmax];
int N,xp,yp;

inline int caut_bin1(int l,int r,int y){
	int m,rez=0;
	while( l<=r ){
		m=l+(r-l)/2;
		if( S[m] <= y ){
			rez=m;
			l=m+1;
		}
		else r=m-1;
	}
	if( !rez ) return ++S[0];
	return rez;
}
inline int caut_bin2(int l,int r,int y){
	int m,rez=0;
	while( l<=r ){
		m=l+(r-l)/2;
		if( S[m] >= y ){
			rez=m;
			r=m-1;
		}
		else l=m+1;
	}
	if( !rez ) return ++S[0];
	return rez;
}

void solve(int wh){
	vector< pair<int,int> >:: iterator it;
	int poz;
	
	memset(S,0,sizeof(S));
	if( wh<=2 ) S[S[0]=1]=-1;
	else S[S[0]=1]=INF;
	for(it=V[wh].begin(); it!=V[wh].end(); ++it){
		if( wh<=2 ) poz=caut_bin1(1,S[0],it->y);
		else poz=caut_bin2(1,S[0],it->y);
		S[poz]=it->y;
	}
}

inline int cmp1(pair<int,int> a, pair<int,int> b){
	return (a.x > b.x || (a.x==b.x && a.y<b.y));
}
inline int cmp2(pair<int,int> a, pair<int,int> b){
	return (a.x < b.x || (a.x==b.x && a.y<b.y));
}
inline int cmp3(pair<int,int> a, pair<int,int> b){
	return (a.x < b.x || (a.x==b.x && a.y>b.y));
}
inline int cmp4(pair<int,int> a, pair<int,int> b){
	return (a.x > b.x || (a.x==b.x && a.y>b.y));
}


int main(){
	int i,x,y,dr_min=0;
	freopen("pachete.in","r",stdin);
	freopen("pachete.out","w",stdout);
	scanf("%d",&N);
	scanf("%d%d",&xp,&yp);
	for(i=1;i<=N;++i){
		scanf("%d%d",&x,&y);
		if( x<xp  && y>=yp ) V[1].pb(mp(x,y)); else
		if( x>=xp && y>=yp ) V[2].pb(mp(x,y)); else
		if( x>=xp && y<yp  ) V[3].pb(mp(x,y)); 
		else V[4].pb(mp(x,y));
	}
	
	for(i=1;i<=4;++i){
		switch( i ){
			case 1 : sort(V[i].begin(),V[i].end(),cmp1); break;
			case 2 : sort(V[i].begin(),V[i].end(),cmp2); break;
			case 3 : sort(V[i].begin(),V[i].end(),cmp3); break;
			case 4 : sort(V[i].begin(),V[i].end(),cmp4); break;
		}
		solve(i);
		dr_min+=S[0];
		if( S[0]==1 && (S[1]==-1 || S[1]==INF) ) dr_min--;
	}
	
	printf("%d\n",dr_min);
	fclose(stdin); fclose(stdout);
	return 0;
}