Cod sursa(job #1240899)

Utilizator tudi98Cozma Tudor tudi98 Data 12 octombrie 2014 12:08:44
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct P{long long x,y;};

vector<P> C[4];
long long Q[50005];

struct comp{
  bool operator()(const P &a,const P &b){
   	if(a.x == b.x) return a.y < b.y;
   	return a.x < b.x;
  }
};

int search(long long Val,int l,int r){
 	while(l != r){
 	 	int mid = (l + r)/2 + 1;
 	 	if(Q[mid] > Val) 
 	 		r = mid - 1;
 	 	else l = mid;
 	}
 	return l;
}

int Solve(int k){
	int N = C[k].size();
	sort(C[k].begin(),C[k].end(),comp());
	int Chains = 0; 
	for(int i = 0; i < N; i++){
		Q[N-i] = -1;
	 	int p = search(C[k][i].y,N-i,N);
	 	if(Chains < N - p + 1) Chains = N - p + 1;
	 	Q[p] = C[k][i].y;
	}
	return Chains;
}

int main(){

	freopen("pachete.in", "r", stdin);
	freopen("pachete.out", "w", stdout);

	int n,X,Y;
	scanf("%d\n%d%d",&n,&X,&Y);
	for(int i = 1; i <= n; i++){
		P a;
        scanf("%lld%lld",&a.x,&a.y);
        if(a.x > X && a.y > Y){ 
            C[0].push_back(a);
        }
        else if(a.x < X && a.y > Y){
            a.x = X - a.x + X;
            C[1].push_back(a);
        }
        else if(a.x < X && a.y < Y){
            a.x = X - a.x + X;
            a.y = Y - a.y + Y; 
            C[2].push_back(a);
        }
        else{
            a.y = Y - a.y + Y;
            C[3].push_back(a);
        }
	}

	int Ans = 0;
	Ans += Solve(0);
	//printf("%d\n",Solve(0));
	Ans += Solve(1);
	//printf("%d\n",Solve(1));
	Ans += Solve(2);
	//printf("%d\n",Solve(2));
	Ans += Solve(3);
	//printf("%d\n",Solve(3));

	printf("%d\n",Ans);
}