Cod sursa(job #31440)

Utilizator lucibitLucian Onea lucibit Data 16 martie 2007 00:08:55
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#define maxn 1001
long x[maxn],y[maxn],n,dx[maxn*maxn],dy[maxn*maxn];
void interclaseaza (long p, long q)
{long m=(p+q)/2;
 long a1[maxn*maxn], a2[maxn*maxn],k1,k2,nr;
 nr=0;
 k1=p;
 k2=m+1;
 while (k1<=m && k2<=q)
 {if(dy[k1]*dx[k2]>=dy[k2]*dx[k1]) {a1[++nr]=dx[k1];
												 a2[nr]=dy[k1];
												  k1++;}
  else {a1[++nr]=dx[k2];
		  a2[nr]=dy[k2];
		  k2++;
			  }

	}
 while (k1<=m)  {a1[++nr]=dx[k1];
					  a2[nr]=dy[k1];
					  k1++;}
 while (k2<=q) {a1[++nr]=dx[k2];
					 a2[nr]=dy[k2];
					  k2++;
				 }

 for(k1=p,k2=1;k1<=q;k1++,k2++)
 {dx[k1]=a1[k2];
  dy[k1]=a2[k2];
	}
}
void sort(long p, long q)
{if(p!=q){sort(p,(p+q)/2);
			 sort((q+p)/2+1, q);
			 interclaseaza(p,q);

			  }
 }

int main()
{long i,NR;
 freopen("trapez.in","r",stdin);
 scanf("%ld\n",&n);
 for(i=1;i<=n;i++)
 {scanf("%ld %ld\n",&x[i],&y[i]);}
 long i1,i2,i3,i4,a,b,n2,nr1;
 NR=0;
 n2=0;
 for(i1=1;i1<n;i1++)
  for(i2=i1+1;i2<=n;i2++)
	  if(y[i1]>y[i2]) {dy[++n2]=y[i1]-y[i2];dx[n2]=x[i1]-x[i2];  }
		 else {dy[++n2]=y[i2]-y[i1];dx[n2]=x[i2]-x[i1];}


 sort(1,n2);

 i1=2;
 while (i1<=n2)
 {nr1=1;
  while (dy[i1]*dx[i1-1]==dy[i1-1]*dx[i1] && i1<=n2)  {i1++;nr1++;}
	NR+=(nr1*(nr1-1))/2;
	if (nr1==1) i1++;

	}
 freopen("trapez.out","w",stdout);
 printf("%ld\n",NR);
return 0;}