Cod sursa(job #195740)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 21 iunie 2008 12:19:47
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include<stdlib.h>
#define NMAX 50000

struct client{
	int x,y,dx,dy,b,c;
	unsigned d;
	};
client a[NMAX],e;
int n;

void poz(int st,int dr,int &piv){
int i=st,j=dr,d=0;
client t;
while(i<j){
	if(a[i].d<a[j].d||
	   a[i].d==a[j].d&&a[i].dx>a[j].dx||
	   a[i].d==a[j].d&&a[i].x==a[j].x&&a[i].y>a[j].y)
		{t=a[i];a[i]=a[j];a[j]=t;d=1-d;}
	i+=d;j-=1-d;
	}
piv=i;
}
void qsrt(int li,int ls){
int piv;
if(li<ls){
	poz(li,ls,piv);
	qsrt(li,piv-1);
	qsrt(piv+1,ls);
	}
}
int main(){
freopen("pachete.in","r",stdin);
freopen("pachete.out","w",stdout);
int i,j,k,nrd=0,c;
client cc;
scanf("%d",&n);
scanf("%d%d",&e.y,&e.x);
for(i=0;i<n;++i){
	scanf("%d%d",&a[i].y,&a[i].x);
	a[i].dx=a[i].x-e.x;
	a[i].dy=a[i].y-e.y;
	a[i].d=(unsigned)abs(a[i].dx)+(unsigned)abs(a[i].dy);
	if(a[i].dx<0&&a[i].dy<=0) a[i].c=1;
	if(a[i].dx<=0&&a[i].dy>0) a[i].c=2;
	if(a[i].dx>0&&a[i].dy<=0) a[i].c=4;
	if(a[i].dx>=0&&a[i].dy>0) a[i].c=3;
	}
qsrt(0,n-1);
for(i=0;i<n;++i){
	if(!a[i].b){
		cc=a[i];
		c=cc.c;
		for(j=i+1;j<n;++j){
			if(a[j].d>=cc.d) continue;
			if(!a[j].b)
				if(abs(a[j].c-c)!=2)
					if((double)a[j].dx*cc.dx>=0&&
					   (double)a[j].dy*cc.dy>=0)
							{
							a[j].b=1;
							cc=a[j];
							}
			}
		a[i].b=1;
		nrd++;
		}
	}
printf("%d",nrd);
return 0;
}