Cod sursa(job #14266)

Utilizator mockeBarca Cristian Mihai mocke Data 8 februarie 2007 17:08:19
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 50001

using namespace std;

struct per { int x, y; } A[NMAX];

int St[NMAX];
int i, N, X, Y, Nr, Sol, K;

bool operator < (const per &a, const per &b)
{
		return (a.x < b.x);
}

int BS1 (int elem, int st, int dr)
{
		int l = st;
		int r = dr;
		int c = 0, pz = dr + 1;
		
		while (l <= r)
		{
			c = (l + r)/2;
			
			if (St[c] > elem) l = c + 1;
			else pz = c, r = c - 1;
		}
		
		return pz;
}

int BS2 (int elem, int st, int dr)
{
		int l = st;
		int r = dr;
		int c = 0, pz = dr + 1;
		
		while (l <= r)
		{
			c = (l + r)/2;
			
			if (St[c] < elem) l = c + 1;
			else pz = c, r = c - 1;
		}
		
		return pz;
}

void op()
{
    Sol += Nr, Nr = 0;
}	

int main()
{
    freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);
	
	scanf("%d %d %d\n", &N, &X, &Y);
    
	for (i= 1; i <= N; i++) scanf("%d %d", &A[i].x, &A[i].y);
    
	sort(A + 1, A + N + 1);
	
    for (i = 1; i <= N; i++)
		if (A[i].x >= X && A[i].y >= Y)
		{
            K = BS1(A[i].y, 0, Nr - 1);
             
			St[K] = A[i].y;
			 
            if (K == Nr) Nr++;
		}
    
	op();
	
    for (i = N; i > 0; i--)
		if (A[i].x <= X && A[i].y >= Y)
		{
            K = BS1(A[i].y, 0, Nr - 1);
             
			St[K] = A[i].y;
			 
            if (K == Nr) Nr++;
		}
    
	op();
	
	for (i = N; i > 0; i--)
		if (A[i].x <= X && A[i].y <= Y)
		{
			K = BS2(A[i].y, 0, Nr - 1);
			
			St[K] = A[i].y;
			
			if (K == Nr) Nr++;
		}
	
	op();
	
	for (i = 1; i <= N; i++)
		if (A[i].x >= X && A[i].y <= Y)
		{
			K = BS2(A[i].y, 0, Nr - 1);
			
			St[K] = A[i].y;
			
			if (K == Nr) Nr++;
		}
    
	op();
		
    printf("%d\n", Sol);
    
    return 0;
}