Cod sursa(job #377748)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 26 decembrie 2009 09:25:33
Problema Trapez Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#define s 0x80000000
#define abs 0x7fffffff
#define N 2000003
#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,c1,c2;
 
 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];
   if(xi==0)c1++;
   else if(yi==0)c2++;
   else
   {
   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(h1<0)h1+=N;
   while((x[h1]!=(xi+semn)||y[h1]!=yi)&&(x[h1]!=0||x[h1]!=0))
   {h1=((LL)B*h1)%N;
    while(h1<0)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;
 }
 S+=(c1*(c1-1))/2;
 S+=(c2*(c2-1))/2;
 printf("%lld",S);
 return 0;
}