Cod sursa(job #10679)

Utilizator TabaraTabara Mihai Tabara Data 28 ianuarie 2007 23:15:43
Problema Patrate 3 Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <fstream>
#include <cmath>
using namespace std;

#define in "patrate3.in"
#define out "patrate3.out"
#define NMAX 1001
#define MOD 666013          //variabila cea mai buna
#define A 0.6180339887 // constanta lui Knuth

#define eps 1e-4

typedef long int INT;
typedef double DO;

typedef struct hash {
        DO x;
        DO y;
        hash *next;
} *PHASH;

PHASH L[MOD];

struct Punct {
       DO x;
       DO y;
} a[NMAX];

int n, nrsol;
DO x_z, y_z, x_u, y_u, x2, y2, x3, y3;
DO mijx, mijy;
DO frac;
INT nr;
DO dx, dy, xa, ya;

void Add( DO x, DO y, INT rest);
int Search( DO x, DO y, INT rest);
void Read();
void Solve();
void Write();

FILE *fout = fopen( out, "w" );

int main()
{
    Read();
    Solve();
    Write();
    
    fclose ( fout );
    return 0;
}

void Read()
{
     FILE *fin = fopen ( in, "r" );
     fscanf( fin, "%d", &n );
     int i;
     DO x, y;
     for ( i = 1; i <= n; ++i )
     {
         fscanf( fin, "%lf%lf", &x, &y );
         a[i].x = x;
         a[i].y = y;
         //calculez tabela de dispersie
         frac = (x*A) - floor(x*A);//partea fractionara
         nr = ((INT)frac)%MOD;//pentru x
         PHASH p = L[nr];
         int ok = 0;
         while ( p && (!ok) )
         {
               if ( fabs(p->x - x) < eps && fabs(p->y - y) < eps ) ok = 1;
               p = p->next;
         }
         if ( ok ) continue;
         Add( x, y, nr );
     }

     fclose ( fin );
}

void Add( DO x, DO y, INT rest )
{
     PHASH p = new hash;
     p->x = x;
     p->y = y;
     p->next = L[rest];
     L[rest] = p;
}

void Solve()
{
     int i, j;
     for ( i = 1; i < n; ++i )
     {
         x_z = a[i].x;
         y_z = a[i].y;
         for ( j = i+1; j <= n; ++j )
         {   
             x_u = a[j].x;
             y_u = a[j].y;
             /*Centrul patratului este mijlocul unei diagonale, deci coordonatele lui sunt 
             mijx = (x0 + x1) / 2 si mijy = (y0 + y1) / 2. Sa notam dx = abs(mijx - x0) si 
             dy = abs(mijy - y0). Se observa ca daca y0 < y1 atunci x2 = mijx + dy, 
             y2 = mijy - dx, x3 = mijx - dy iar y3 = mijy + dx. In caz contrar, 
             avem x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.
             */
             mijx = ( x_z + x_u ) / 2;
             mijy = ( y_z + y_u ) / 2;
             dx = fabs( mijx - x_z );
             dy = fabs( mijy - y_z );
             if ( y_z < y_u )
             {
                  x2 = mijx + dy;
                  y2 = mijy - dx;
                  x3 = mijx - dy;
                  y3 = mijy + dx; 
             }
             else
             {
                  x2 = mijx - dy;
                  y2 = mijy - dx;
                  x3 = mijx + dy;
                  y3 = mijy + dx;              
             }
             xa = x2;
             ya = y2;
             frac = (xa*A) - floor(xa*A);
             nr = ((INT)frac)%MOD;
             int ok1 = Search( xa, ya, nr ); 
             
             xa = x3;
             ya = y3;
             frac = (xa*A) - floor(xa*A);
             nr = ((INT)frac)%MOD;
             int ok2 = Search( xa, ya, nr );
             
             //fprintf( fout, "%d %d\n", ok1, ok2 );
             if ( ok1 == 1 && ok2 == 1 ) nrsol++;
         }
     }
}

int Search( DO x, DO y, INT rest )
{
    PHASH p = L[rest];
    int ok = 0;
    while ( p && (!ok) )
    {
          if ( fabs(p->x - x) < eps && fabs(p->y - y) < eps ) ok = 1;
          p = p->next;
    }
    if ( ok ) return 1;
    else return 0;
}

void Write()
{
     fprintf( fout, "%d\n", nrsol );
}