Cod sursa(job #11609)

Utilizator TabaraTabara Mihai Tabara Data 31 ianuarie 2007 22:01:49
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 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(double,double);
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 QSort( int st, int dr )
{
     /*double pivot = a[st].x;
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( (pivot - a[i].x) >= eps || fabs( a[i].x - pivot)< eps && (a[st].y - a[i].y)>= eps  );
         do { j--; } while ( (a[j].x - pivot ) >= eps || fabs( a[j].x - pivot)<eps && (a[j].y - a[st].y ) >= eps  );
         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 );*/
     int i = st-1;
     int j = dr+1;
     double piv = a[st].x;
     double piv2 = a[st].y;
     
     while ( i <= j )
     {
           do { i++; } while (  (piv - a[i].x) >= eps ||  ( fabs(piv-a[i].x) < eps && (piv2-a[i].y) >= eps ));
           do { j--; } while (  (a[j].x - piv) >= eps ||  ( fabs(a[j].x-piv) < eps && (a[j].y-piv2) >= eps ));
           if ( i <= j )
           {
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
           }
     }
     
     if ( st < j ) QSort(st,j);
     if ( i < dr ) QSort(i,dr);
}

void Solve()
{
     int i, j;
     for ( i = 1; i < n; ++i )
     {    
         for ( j = i + 1; j <= n; ++j )
         {
             x_z = a[i].x;
             y_z = a[i].y;
             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;
             
             gasit = false;
             BS ( xa, ya );
             bool ok1 = gasit;
             
             xa = x3;
             ya = y3;
             
             gasit = false;
             BS ( xa, ya );
             bool ok2 = gasit;
             
             if ( ok1 == true && ok2 == true ) 
             {
                  nrsol++;
             }
         }
     }
}

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

void BS(double xa, double ya)
{
     int bl = 1,br = n, bm;//asta cred ca e buna
     while ( bl <= br )
     {
           bm = (br+bl)>>1;
           if ( a[bm].x - xa >= eps ) br = bm - 1;
           else
           {
               if ( xa - a[bm].x >= eps ) bl = bm + 1;
               else if ( fabs( a[bm].x - xa ) < eps )
               {
                    if ( a[bm].y - ya >= eps )
                    {
                         br = bm - 1;
                    }
                    else if ( ya - a[bm].y >= eps )
                    {
                         bl = bm + 1;
                    }
                    if ( fabs(a[bm].y  - ya ) < eps )  gasit = true, bl = br + 1;
               }
           }
     }             
}