Pagini recente » Cod sursa (job #849865) | Cod sursa (job #226259) | Cod sursa (job #3264872) | Cod sursa (job #587021) | Cod sursa (job #362879)
Cod sursa(job #362879)
#include<stdio.h>
#include<algorithm>
using namespace std;
int x0,y0,i,j,n,k,sol,v[50010];
struct firma{int x , y ; } x[50010];
int cmp(firma a,firma b){
return a.x < b.x;
}
int cbin(int val , int u){
int m,poz , p = 1;
while(p <= u){
m = (p +u )>>1;
if(v[ m ] <= val) {poz = m; u = m - 1;}
else
p = m + 1;}
return poz;
}
void solve ( int n){
int p = 1,u = 1,i,poz;
for( i =2 ; i <= n; i++)
{if(v[ i ] < v[ u ])
{u++;v[ u ] = v[ i ];}
else{
poz = cbin(v[ i ], u);
v[ poz ] = v[ i ];
}
}
sol+= u - p + 1;
}
int main(){
freopen("pachete.in" , "r" , stdin);
freopen("pachete.out" , "w" , stdout);
scanf("%d%d%d" , &n , &x0 , &y0);
for(i = 1 ; i <= n ; i++)
scanf("%d%d" , &x[ i ].x , &x[ i ].y);
sort(x + 1 , x + 1 + n , cmp);
k = 0;
//primul cadran
for( i = 1 ; i <= n ; i++)
if(x[ i ].x >= x0 && x[ i ].y >= y0)
{k++;v[ k ] = x[ i ].y;}
if(k)
solve( k );
//al 2-lea cadran
k = 0;
for( i = n ; i >= 1 ;i--)
if(x[ i ].x > x0 && x[ i ].y < x0)
{k++;v[ k ] = x[ i ].y;}
if(k)
solve( k );
//al 3-lea cadran
k = 0;
for(i = n ; i >= 1 ;i--)
if(x[ i ].x <= x0 && x[ i ].y <= y0)
{k++; v[ k ] = y0 - x[ i ].y;}
if(k)
solve( k );
// ultimul cadran
k = 0 ;
for(i = 1 ; i <= n ;i++)
if(x[ i ].x > x0 && x[ i ].y < y0)
{k++; v[ k ] = y0 - x[ i ].y;}
if(k)
solve( k );
printf("%d" , sol);
return 0;}