Cod sursa(job #6945)

Utilizator marius_902002Cocis Marius Gabriel marius_902002 Data 21 ianuarie 2007 11:04:22
Problema Pachete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 0.94 kb
#include<stdio.h>
#include<math.h>
long n,x,y,x0,y0,i,k;

long divide(int p,int q);
void qsort(int p,int q);
void parc(int i);
typedef struct{
	long x,y,v,p;
}e;

e s[50001];

int main(){

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

scanf("%ld",&n);

scanf("%ld%ld",&x0,&y0);
for(i=1;i<=n;i++){
	scanf("%ld%ld",&s[i].x,&s[i].y);
	s[i].v=0;
	s[i].p=(s[i].y-y0)/(s[i].x-x0);
}
qsort(1,n);
k=n;
parc(1);
printf("%ld",k);
return 0;
}

long divide(int p,int q)
{
	long st=p,dr=q,x=s[p].p;
	while(st<dr)
	{
		while(st<dr && s[dr].p>=x)
			dr--;

		s[st].p=s[dr].p;
		while(st<dr &&s[st].p<=x)
			st++;
		s[dr].p=s[st].p;
	}
	s[st].p=x;
	return st;


}
void qsort(int p,int q)
{
	long m=divide(p,q);
	if(m-1>p)
		qsort(p,m-1);
	if(m+1<q)
		qsort(m+1,q);
}
void parc(int i){
	long j;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			if(s[i].p!=s[j].p){
				k=k-(j-i-1);
				break;
			}
}