Cod sursa(job #362879)

Utilizator ConsstantinTabacu Raul Consstantin Data 11 noiembrie 2009 11:10:25
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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;}