Cod sursa(job #10828)

Utilizator TabaraTabara Mihai Tabara Data 29 ianuarie 2007 18:14:58
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <fstream>
#include <cmath>
using namespace std;

#define in "patrate3.in"
#define out "patrate3.out"
#define NMAX 1001

#define eps 1e-4

struct Punct {
       double x;
       double y;
} a[NMAX], aux;

int n, nrsol;
bool gasit = false;
double x_z, y_z, x_u, y_u, x2, y2, x3, y3;
double mijx, mijy;
double dx, dy, xa, ya;

void BS(int,int);
void Read();
void Solve();
void QSort( int, int );
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;
     double x, y;
     for ( i = 1; i <= n; ++i )
     {
         fscanf( fin, "%lf%lf", &x, &y );
         a[i].x = x;
         a[i].y = y;
     }
     QSort( 1, n );
     fclose ( fin );
}
/*
void Debug()
{
     int i;
     for ( i = 1; i <= n; ++i )
     {
         fprintf( fout, "%lf %lf\n", a[i].x, a[i].y );
     }
}*/
//sorteaza perfect
void QSort( int st, int dr )
{
     double pivot = a[st].x;
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( a[i].x < pivot||( fabs( a[i].x - pivot)<eps && a[i].y < a[st].y ) );
         do { j--; } while ( a[j].x > pivot||( fabs( a[j].x - pivot)<eps && a[j].y > a[st].y ) );
         if ( i <= j )
         {
              aux = a[i];
              a[i] = a[j];
              a[j] = aux;
         }
     } while ( i <= j );
     if ( i < dr ) QSort ( i, dr );
     if ( st < j ) QSort ( st, j );
}

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;
             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;/*
             xa = a[i].x;
             ya = a[i].y;*/
             
             gasit = false;
             BS ( i, j );
             bool ok1 = gasit;
             
             xa = x3;
             ya = y3;
             /*
             xa = a[j].x;
             ya = a[j].y;*/
             
             gasit = false;
             BS ( i, j );
             bool ok2 = gasit;
             //fprintf ( fout, "%d %d\n", ok1, ok2 );
             if ( ok1 == true && ok2 == true ) 
             {
                  nrsol++;
                  //fprintf ( fout, "Initial\n%lf %lf si %lf %lf\n pentru care am format\n%lf %lf si %lf %lf\n\n", 
                    //
                    //                     a[i].x, a[i].y, a[j].x, a[j].y, x2, y2, x3, y3 );
             }
         }
     }
}

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

void BS( int st, int dr )
{
     int mij = (st + dr) >> 1;
     if ( fabs( a[mij].x - xa ) < eps &&
          fabs( a[mij].y - ya ) < eps )
          {
                     gasit = true;
                     return;
          }
     if ( xa < a[mij].x ) 
     {
          if ( st < mij )
             BS ( st, mij  );
          else 
          {
               gasit = false;
               return;
          }
     }
     if ( xa > a[mij].x )
     {
          if ( mij + 1 < dr ) 
             BS ( mij + 1, dr );
          else 
          {
               gasit = false;
               return;
          }
     }
}