Cod sursa(job #315685)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 16 mai 2009 20:23:44
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<stdlib.h>
struct im{long long x,y;}p[1000005];
long long n,i,j,a[1005],b[1005],lp,x,sum;
long long partit(im a[],long long st,long long dr)
{long long i,j,m;
 im piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].x*piv.y<piv.x*a[i].y);
   do{--j;} while(a[j].x*piv.y>piv.x*a[j].y);
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(im a[],long long st,long long dr)
{long long  p;
 if (st<dr)
   {p=partit(a,st,dr);
	quicks(a,st,p);
	quicks(a,p+1,dr);
   }
}
int main()
{
 freopen("trapez.in","r",stdin);
 freopen("trapez.out","w",stdout);
 scanf("%lld",&n);
 for(i=1;i<=n;++i)
    {scanf("%lld%lld",&a[i],&b[i]);
     for(j=1;j<i;++j){p[++lp].x=a[i]-a[j];p[lp].y=b[i]-b[j];if(p[lp].y<0){p[lp].y*=-1;p[lp].x*=-1;}}}
 quicks(p,1,lp);
 x=1;
 for(i=2;i<=lp;++i)
    if(p[i-1].x*p[i].y==p[i].x*p[i-1].y)
      x++;
      else{sum+=((x*(x-1))/2);x=1;}
 printf("%lld\n",sum);
 return 0;
}