Cod sursa(job #447893)

Utilizator alexeiIacob Radu alexei Data 1 mai 2010 19:25:31
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct{
	int x,y;
}list;

vector< list > C1,C2,C3,C4;

inline bool cmp1( list A, list B )
{
	return A.x<B.x;
}

inline bool cmp2( list A, list B )
{
	return A.x>B.x;
}

vector< int > D;

void lowerbound( int Y )
{
	int inc=0, sf=D.size()-1;
	int mij;
	int ans;
	
	while( inc<=sf )
	{
		mij=(inc+sf)>>1;
		
		if( D[mij]<Y )
		{
			ans=mij;
			sf=mij-1;
		}
		else
		{
			inc=mij+1;
		}
	}
	
	D[ans]=Y;
}

void upperbound( int Y )
{
	int inc=0, sf=D.size()-1;
	int mij,ans;
	
	while( inc<=sf )
	{
		mij=(inc+sf)>>1;
		
		if( D[mij]>Y )
		{
			ans=mij;
			sf=mij-1;
		}
		else
		{
			inc=mij+1;
		}
	}
	
	D[ans]=Y;
}

int main()
{
	freopen("pachete.in","r",stdin);
	freopen("pachete.out","w",stdout);
	
	int N,ANS=0;
	scanf("%d",&N);
	
	int PX,PY;
	scanf("%d%d",&PX,&PY);
	
	int a1,a2;
	int i;
	for(i=1; i<=N; ++i)
	{
		scanf("%d%d",&a1,&a2);
		
		list X;
		X.x=a1;
		X.y=a2;
		
		if( a1>PX && a2>PY )
			C1.push_back( X );
		if( a1<PX && a2>PY )
			C2.push_back( X );
		if( a1<PX && a2<PY )
			C3.push_back( X );
		if( a1>PX && a2<PY )
			C4.push_back( X );
	}
	
	sort( C1.begin(), C1.end(), cmp1 );
	sort( C2.begin(), C2.end(), cmp2 );
	sort( C3.begin(), C3.end(), cmp2 );
	sort( C4.begin(), C4.end(), cmp1 );
	
	vector< list >::iterator it,check;
	
	int s;
	
	for( it=C1.begin(); it!=C1.end(); ++it )
	{
		a1=it->x;
		a2=it->y;
		
		if( D.empty() )
		{
			D.push_back( a2 );
			continue;
		}
		s=D[D.size()-1];
		
		if( s > a2 )
		{
			D.push_back( a2 );
			continue;
		}
		
		lowerbound( a2 );
	}
	
	if( !D.empty() )
		ANS+=D.size();
	
	D.clear();
	
	for( it=C2.begin(); it!=C2.end(); ++it )
	{
		a1=it->x;
		a2=it->y;
		
		if( D.empty() )
		{
			D.push_back( a2 );
			continue;
		}
		s=D[D.size()-1];
		
		if( s > a2 )
		{
			D.push_back( a2 );
			continue;
		}
		
		lowerbound( a2 );
	}
	
	if( !D.empty() )
		ANS+=D.size();
	
	D.clear();
	
	for( it=C3.begin(); it!=C3.end(); ++it )
	{
		a1=it->x;
		a2=it->y;
		
		if( D.empty() )
		{
			D.push_back( a2 );
			continue;
		}
		s=D[D.size()-1];
		
		if( s < a2 )
		{
			D.push_back( a2 );
			continue;
		}
		
		upperbound( a2 );
	}
	
	if( !D.empty() )
		ANS+=D.size();
	
	D.clear();
	
	for( it=C4.begin(); it!=C4.end(); ++it )
	{
		a1=it->x;
		a2=it->y;
		
		if( D.empty() )
		{
			D.push_back( a2 );
			continue;
		}
		s=D[D.size()-1];
		
		if( s < a2 )
		{
			D.push_back( a2 );
			continue;
		}
		
		upperbound( a2 );
	}
	
	if( !D.empty() )
		ANS+=D.size();
	
	D.clear();
	
	printf("%d\n",ANS);
	
	return 0;
}