Cod sursa(job #46487)

Utilizator razvi9Jurca Razvan razvi9 Data 2 aprilie 2007 18:09:58
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#define inf 2000000010.0
#define abs(a) a>0?a:-a
int a[500000][2],b[1001][2],C,n,m,i,j,c[1000];
long long nr,NR;
int poz(int st,int dr)
{int x=1,y=0,aux;
 while(st<dr)
 {if(a[st][0]*a[dr][1]>a[dr][0]*a[st][1] || (a[st][1]==0 && a[dr][0]!=0)) 
  {aux=a[st][1];a[st][1]=a[dr][1];a[st][1]=aux;aux=a[st][0];a[st][0]=a[dr][0];a[dr][0]=aux;
   aux=x;x=-y;y=-aux;}
  st=st+x;dr=dr+y;}
 return st;}
void qsort(int st,int dr)
{if(st>=dr) return;
 int k=poz(st,dr);
 qsort(st,k-1);
 qsort(k+1,dr);}
int cmmdc(int a,int b)
{if(b==0) return a;
 return cmmdc(b,a%b);}
int main()
{freopen("trapez.in","r",stdin);
 freopen("trapez.out","w",stdout);
 scanf("%d",&n);
 c[2]=1;
 for(i=3;i<=n;i++)
  c[i]=c[i-1]*i/(i-2);
 for(i=1;i<=n;i++)
 {scanf("%d %d",&b[i][0],&b[i][1]);
  for(j=1;j<i;j++)
  {a[++m][0]=b[i][0]-b[j][0],a[m][1]=b[i][1]-b[j][1];
   C=a[m][1]==0?1:cmmdc(abs(a[m][1]),abs(a[m][0]));
   a[m][0]=a[m][0]/C;
   a[m][1]=a[m][1]/C;}}
 qsort(1,m);
 nr=1;
 for(i=2;i<=m;i++)
  if((a[i][1]==a[i-1][1]&&a[i][0]==a[i-1][0])||(a[i][1]==0&&a[i-1][1]==0||a[i][0]==0&&a[i-1][0]==0)) nr++;
  else NR+=c[nr],nr=1;
 printf("%d",NR);
 fclose(stdout);
 return 0;}