Cod sursa(job #73991)

Utilizator a7893Nae Mihai a7893 Data 23 iulie 2007 12:03:22
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<stdlib.h>
#define N 50000
int n,k,x1,y1;
struct vec{
	int x,y;
}a[N],sol[N];
void read()
{
	int i;
	scanf("%d",&n);
	//scanf("%d%d",&x1,&y1);
	n++;
	for(i=0;i<n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
}
int search(int poz)
{
	int i;
	for(i=0;i<k;i++)
		if(sol[i].y<a[poz].y)
			return i;
	return k+1;
}
int maxim(const void *a,const void *b)
{
	vec *aa,*bb;
	aa=(vec*)a;
	bb=(vec*)b;
	return aa->x-bb->x;
}
void solve()
{
	int i,poz;
	//sol[k].x=x1;
	//sol[k++].y=y1;
	qsort(a,n,sizeof(a[0]),maxim);
	sol[k++]=a[0];
	for(i=1;i<n;i++)
	{
		poz=search(i);
		if(poz>k)
			sol[k++]=a[i];
		else
			sol[poz]=a[i];
	}
	printf("%d\n",k);
}
int main()
{
	freopen("pachete.in","r",stdin);
	freopen("pachete.out","w",stdout);
	read();
	solve();
	return 0;
}