Cod sursa(job #16504)

Utilizator devilkindSavin Tiberiu devilkind Data 13 februarie 2007 14:06:59
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#define NMAX 1001
#define modulo 301093

struct pct{long int x,y;};

struct hash{long int x,y,ap;
            hash *urm;} *vf[modulo];

FILE *f = fopen("trapez.in","rt"), *g = fopen("trapez.out","wt");

long int n,i,j,k,nrv,x,y,div,x1,x2,y1,y2,val,sol;
pct a[NMAX];

long int cmmdc(long int a, long int b)
{
long int r;     
while (b)
      {
      r=a%b;
      a=b;
      b=r;
      }
return a;
}

void citire()
{
hash *p;
long int ok;
fscanf(f,"%ld",&n);
for (i=1;i<=n;i++)
    {
    fscanf(f,"%ld %ld",&x1,&y1);
    a[i].x=x1;
    a[i].y=y1;
    for (j=1;j<=i-1;j++)
        {
        x2=a[j].x;
        y2=a[j].y;
        x=x1-x2;
        y=y1-y2;
	if (x==0) {sol+=nrv;nrv++;}
        else 
        {
	div=cmmdc(y,x);
	x/=div;
	y/=div;
	if (y==0) {x=0;y=0;}
	val=(x^y)%666013;
    if (val<0) val*=-1;
    p=vf[val];
    ok=0;
    while (p)
          {if ((p->x==x)&&(p->y==y)) {p->ap++;
                                     ok=1;break;}
          p=p->urm;
          }
    if (!ok) {p=new hash;
             p->x=x;
	     p->y=y;
	     p->ap=1;
	     p->urm=vf[val];
	     vf[val]=p;
             }
	     else sol+=p->ap-1;
         }
    }
    }  
fprintf(g,"%ld",sol);
}


int main()
{
citire();
fclose(f);
fclose(g);
return 0;
}