Cod sursa(job #8258)

Utilizator cos_minBondane Cosmin cos_min Data 23 ianuarie 2007 23:35:39
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <stdio.h>
#include <math.h>

#define in "patrate3.in"
#define out "patrate3.out"
#define eps 0.00001
#define dim 1001

struct punct {
       double x, y;
} a[dim];

int n;

void Qsort(int,int);
int BinaryS(double i, double j);

int main()
{
    int t=0;
    double x0, y0, x1, y1, x2, y2, x3, y3, mijx, mijy, dx, dy;
    double x_, y_;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d",&n);
    
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%lf%lf",&x_,&y_);
        a[i].x = x_;
        a[i].y = y_;
    }
    
    Qsort(1,n);
    
 /* for ( int i = 1; i <= n; i++ )
    {
        printf("%lf %lf\n",a[i].x,a[i].y);
    }*/
    
    for ( int i = 1; i < n; i++ )
    {
        for ( int j = i+1; j <= n; j++ )
        {
            x0 = a[i].x; y0 = a[i].y;
            x1 = a[j].x; y1 = a[j].y;
            mijx = (x0 + x1) / 2; mijy = (y0 + y1) / 2;
            dx = fabs(mijx - x0); dy = fabs(mijy - y0);
            
            if ( y0 < y1 )
            {
                 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;
            }
            
           // printf("%lf %lf %lf %lf %d %d\n", x2,y2, x3, y3, BinaryS(x2,y2), BinaryS(x3,y3));
            
            if ( BinaryS(x2,y2) == 1 && BinaryS(x3,y3) ) t += 1;
        }
    }   
      
    printf("%d",t/2);     
}

void Qsort(int st, int dr)
{
     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 )
           {
                punct aux = a[i];
                a[i] = a[j];
                a[j] = aux;
           }
     }
     
     if ( st < j ) Qsort(st,j);
     if ( i < dr ) Qsort(i,dr);
}

int BinaryS(double i, double j)
{
    int st = 1;
    int dr = n;
    int mij = (st+dr)/2;
    int ok = 0;
    
    while ( st <= dr )
    {
          mij = (st+dr)/2;
          if ( a[mij].x - i >= eps ) 
          {
               dr = mij-1;
          }
          else
          {
              if ( i - a[mij].x >= eps )
              {
                   st = mij+1;
              }
              else 
              if ( fabs(a[mij].x - i)  < eps ) 
              {
                   if ( a[mij].y - j >= eps ) 
                   {
                      dr = mij-1;
                   }
                   else 
                   if ( j-a[mij].y >= eps )
                   {
                      st = mij+1;
                   }
                   
                   if ( fabs(a[mij].y - j) < eps ) ok = 1, st = dr+1;
              }
          }
    }
    
    return ok;
}