Cod sursa(job #364826)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 17 noiembrie 2009 01:39:27
Problema Trapez Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
#define M 1001
int c[N],d[N],vf;
int x[N],y[N];

int cmmdc(int a,int b)
{if(a%b==0)
  return b;
 else
  return cmmdc(b,a%b);
}

void quick(int stanga, int dreapta)
{int st=stanga,dr=dreapta,pm=st+rand()%(dr-st+1),q=10000*c[pm]+d[pm],aux1,aux2;
 while(st<dr)
 {while(c[st]*10000+d[st]<q){st++;}
  while(c[dr]*10000+d[dr]>q){dr--;}
  if(st<=dr)
  {aux1=c[st];c[st]=c[dr];c[dr]=aux1;
   aux2=d[st];d[st]=d[dr];d[dr]=aux2;
   st++;
   dr--;
  }
 }
 if(stanga<dr)
 {quick(stanga,dr);
 }
 
 if(st<dreapta)
 {quick(st,dreapta);
 }
}

int main()
{freopen("trapez.in","r",stdin);
 freopen("trapez.out","w",stdout);
 int i,j,r,t,n,cmm;
 scanf("%d",&n);
 for (i=0;i<n;i++)
 {scanf("%d %d",&x[i],&y[i]);}
 r=t=0;
 for (i=0;i<n-1;i++)
 {for (j=i+1;j<n;j++)
  {if(x[i]==x[j])
   {r++;
   }
   else if(y[i]==y[j])
   {t++;
   }
   
   else
   {cmm=cmmdc(abs(x[i]-x[j]),abs(y[i]-y[j]));
    c[vf]=abs(x[i]-x[j])/cmm;
    d[vf]=abs(y[i]-y[j])/cmm;
    if((x[i]-x[j])*(y[i]-y[j])<0)
    {c[vf]*=-1;
    }
    vf++;
   }
  }
 }
 quick(0,vf-1);
 int s=0;
 for (i=0,j=0;i<vf;i++)
 {if(c[i]==c[i+1]&d[i]==d[i+1])
  {j++;}
  else
  {s+=(j*(j+1))/2;
   j=0;
  }
 }
 s+=r*(r-1)/2+t*(t-1)/2;
 printf("%d",s);
 return 0;
}