Cod sursa(job #496392)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 28 octombrie 2010 20:00:25
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 50010

struct punct
{
	int x, y;
} v[nmax];

int cmp (punct a, punct b)
{
	return a.x<b.x;
}

int n, X, Y, vx[5][nmax], vy[5][nmax], p[5], l, sol, s[nmax];

int search(int a, int b, int x)
{
	int m, r=0;
	while (a<=b)
	{
		m=(a+b)/2;
		if (s[m]<=x) 
		{
			r=m;
			b=m-1;
		} else a=m+1;
	}
	return r;
}

void solve()
{
	sort (v+1, v+l+1, cmp);
	int i, h=0, p;
	for (i=1; i<=l; i++)
	{
		p=search(1,h,v[i].y);
		if (!p) 
			s[++h]=v[i].y; else
			s[p]=v[i].y;
	}
	sol+=h;
}

int main()
{
	freopen("pachete.in","r",stdin);
	freopen("pachete.out","w",stdout);
	scanf("%d",&n);
	scanf("%d %d",&X,&Y);
	int i, x, y, c=0, j;
	for (i=1; i<=n; i++)
	{
		scanf("%d %d",&x,&y);
		if (x>=X && y>Y) c=1; else
		if (x<X && y>=Y) c=2; else
		if (x<=X && y<Y) c=3; else
		if (x>X && y<=Y) c=4;
		p[c]++;
		vx[c][p[c]]=x;
		vy[c][p[c]]=y;
	}
	for (i=1; i<=4; i++)
	{
		l=p[i];
		for (j=1; j<=l; j++) 
		{
			v[j].x=vx[i][j];
			if (v[j].x<X) v[j].x=X-v[j].x;
			v[j].y=vy[i][j];
			if (v[j].y<Y) v[j].y=Y-v[j].y;
		}
		solve();
	}
	printf("%d\n",sol);
}