Cod sursa(job #377744)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 26 decembrie 2009 09:02:37
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#define s 0x80000000
#define abs 0x7fffffff
#define N 1000003
#define A 30103
#define B 660013
#define M 1002
typedef long long int LL;
//hash
int x[N],y[N],count[N];
//
int xread[M],yread[M];
int cmmdc(int x,int y)
{if(x<y)
 return cmmdc(y,x);
 int t;
 while(y)
 {t=x%y;
  x=y;
  y=t;
 }
 return x;
}
int main ()
{freopen("trapez.in","r",stdin);
 freopen("trapez.out","w",stdout);
 int i,j,n,vf,xi,yi,semn,c;
 
 LL h1,S=0;
 scanf("%d",&n);
 for (i=0;i<n;i++)
 {scanf("%d %d",&xread[i],&yread[i]);
 }
 for (i=0;i<n-1;i++)
 {for (j=i+1;j<n;j++)
  {xi=xread[j]-xread[i];
   yi=yread[j]-yread[i];
   c=cmmdc(xi,yi);
   xi/=c;
   yi/=c;
   semn=((xi&s)^(yi&s));
   xi=xi&abs;
   yi=yi&abs;

   h1=((LL)(xi+semn)*(LL)A+(LL)yi*(LL)B)%(LL)N;
   while((x[h1]!=(xi+semn)||y[h1]!=yi)&&(x[h1]!=0||x[h1]!=0))
   {h1=((LL)B*h1)%N;
   }
   if(x[h1]==0&&y[h1]==0)
   {x[h1]=xi+semn;
    y[h1]=yi;
   }
    count[h1]++;
  }
 }
 for (i=0;i<N;i++)
 {S+=(LL)count[i]*(LL)(count[i]-1)/2LL;
 }
 printf("%lld",S);
 return 0;
}