Cod sursa(job #16533)

Utilizator devilkindSavin Tiberiu devilkind Data 13 februarie 2007 15:51:49
Problema Patrate 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <math.h>
#define NMAX 1001
#define HMAX 666013
#define eps 1e-5

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

struct hash{double x,y;
            hash *urm;} *vf[HMAX];                          

double a[NMAX][2];
long int n,i,j,k,x,y,val,sol=0;

void citire()
{
fscanf(f,"%ld",&n);
hash *p;
for (i=1;i<=n;i++) 
    {
    fscanf(f,"%lf %lf",&a[i][0],&a[i][1]);
    x=(long int) a[i][0];
    if (x<0) x*=-1;
    y=(long int) a[i][1];
    if (y<0) y*=-1;
    x=(x^y)%HMAX;;
    p=new hash;
    p->x=a[i][0];
    p->y=a[i][1];
    p->urm=vf[x];
    vf[x]=p;
    } 
}

int find(double x, double y)
{
long int val,x1,y1;
hash *p;
x1=(long int) x;
y1=(long int) y;
if (x1<0) x1*=-1;
if (y1<0) y1*=-1;
val=(x1^y1)%HMAX;
p=vf[val];
while (p)
      {if ((fabs(p->x-x)<eps)&&(fabs(p->y-y)<eps)) return 1;
      p=p->urm;
      }
return 0;
}

void check()
{
double x0,y0,x1,y1,mijx,mijy,x2,x3,y2,y3,dx,dy;
int ok1,ok2;
x0=a[i][0];
y0=a[i][1];
x1=a[j][0];
y1=a[j][1];

mijx=(x0+x1)/2;
mijy=(y0+y1)/2;

dx=fabs(mijx-x0);
dy=fabs(mijy-y0);

if (y0<y1) {x2=mijx+dy;
	   y3=mijy-dx;

	   x3=mijx-dy;
	   y2=mijy+dx;
           }
           else 
           {
           x2=mijx+dy;
           y2=mijy+dx;
           
           x3=mijx-dy;
           y3=mijy-dx;
           }
ok1=find(x2,y2);
ok2=find(x3,y3);

if (ok1&&ok2) sol++;
}


void solve()
{
for (i=1;i<=n;i++)
    for (j=i+1;j<=n;j++)
        check();
fprintf(g,"%ld",sol);
}


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