Pagini recente » Borderou de evaluare (job #3181567) | Cod sursa (job #2109422) | Cod sursa (job #728479) | Cod sursa (job #2317910) | Cod sursa (job #447893)
Cod sursa(job #447893)
#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;
}