Cod sursa(job #163384)

Utilizator numaibuncaeleviprofu de tic numaibuncaelevi Data 22 martie 2008 06:40:05
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
//#include<conio.h>
#define NMAX	1000

struct pct { int x,y; };
struct rpt { int dx,dy; };

int cmp(rpt a,rpt b)
{
return ((long long)a.dy*b.dx>(long long)b.dy*a.dx);
}

void poz(int st,int dr,int &piv,rpt x[])
{int i=st,j=dr,d=0;
 rpt	t;
 while(i<j) { if(cmp(x[i],x[j]))
					{
					t=x[i];x[i]=x[j];x[j]=t;
					d=1-d;
					}
			  i+=d;
			  j-=1-d;
			}
 piv=i;
}

void qsrt(int left,int right,rpt x[])
{int piv;
 if(left<right) {poz(left,right,piv,x);
				 qsrt(left,piv-1,x);
				 qsrt(piv+1,right,x);
				}

}

int egal(rpt a,rpt b)
{
return ((long long)a.dy*b.dx==(long long)b.dy*a.dx);
}

int main()
{
freopen("trapez.in","r",stdin);
freopen("trapez.out","w",stdout);
int n,i,j,k,e,nrtrpz;
pct	v[1000]={{0,0}};
rpt r[NMAX*(NMAX-1)/2]={{0,0}};
scanf("%d",&n);
i=0;
while(i<n) { scanf("%d%d",&v[i].x,&v[i].y);i++;}
k=0;
for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		{r[k].dx=v[i].x-v[j].x;r[k].dy=v[i].y-v[j].y;k++;}
qsrt(0,k-1,r);
nrtrpz=0;
i=0;
while(i<k-1) {j=i+1;e=1;
			  while(egal(r[i],r[j])){ j++; e++;}
			  if(e>1) nrtrpz+=e*(e-1)/2;
			  i=j;
			 }
printf("%d",nrtrpz);
return 0;
}