Cod sursa(job #89051)

Utilizator floringh06Florin Ghesu floringh06 Data 5 octombrie 2007 15:55:16
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.89 kb
/* O (N) memorie
 * O (N^2 log N) timp
 * Sortare abs/ord cu cautare binara
 */

#include <cstdio>
#include <math.h>

using namespace std;

#define FIN "patrate3.in"
#define FOUT "patrate3.out"
#define MAX_N 1 << 11

const double eps = 0.0001;

typedef struct 
{
    double x;
    double y;
} point ;
 
int N, i;
int BEST; // solutia

point A[MAX_N >> 1];

      int part (int st, int dr)
      {
          int i, j, s = 1;
          i = st; j = dr;
          while (i < j)
          {
                if (A[i].x - A[j].x > eps)
                {
                   point d = A[i]; 
                   A[i] = A[j];
                   A[j] = d;
                   s = 1 - s;
                }
                if (fabs (A[i].x - A[j].x) < eps && A[i].y - A[j].y > eps)
                {
                   point d = A[i]; 
                   A[i] = A[j];
                   A[j] = d;
                   s = 1 - s;
                }
                if (s) ++i; else --j;
          }
          return i;
      }

      void sort (int st, int dr)
      {
           if (st < dr)
           {
                int p = part (st, dr);
                sort (st, p - 1);
                sort (p + 1, dr);
           }
      }  
      
      int bsearch (point P)
      {
          int li, lf, m;
          int f = 0; // gasit ?
          li = 1; lf = N; 
          while (li <= lf)
          {
              m = (li + lf) >> 1;
              if (double (fabs (P.x - A[m].x)) < eps && double (fabs (P.y - A[m].y)) < eps )
               { 
                 f = 1;
                 break ;
               }
              if (double (P.x - A[m].x) > eps) li = m + 1;  // x > mid
              if (double (A[m].x - P.x) > eps) lf = m - 1;  // x < mid
              if (double (fabs (P.x - A[m].x)) < eps)  // x = mid
              {
                    if (double (P.y - A[m].y) > eps) li = m + 1;  // y > mid     
                    if (double (A[m].y - P.y) > eps) lf = m - 1;  // y < mid
              }
          }
          return f;         
      }
      
      void solve ( void )
      {
            int i, j;
            point p0, p1; // diagonala fixata
            point p2, p3; // punctele calculate
            point mid; 
            for (i = 1; i <= N - 1; ++i)
               for (j = i + 1; j <= N; ++j)
               {
                   p0 = A[i]; p1 = A[j]; 
                   mid.x = double ((A[i].x + A[j].x) / 2);
                   mid.y = double ((A[i].y + A[j].y) / 2);  
                   double dx = double ((fabs (mid.x - p0.x)));
                   double dy = double ((fabs (mid.y - p0.y)));
                   if (double ((p1.x - p0.x) * (p1.y - p0.y)) <= 0)
                   {
                       // left
                       p2.x = double (mid.x + dy);
                       p2.y = double (mid.y + dx);       
                       p3.x = double (mid.x - dy);
                       p3.y = double (mid.y - dx);       
                       if (bsearch (p2) && bsearch (p3)) ++ BEST;
                   }
                   else 
                   {
                       // right      
                       p2.x = double (mid.x - dy);
                       p2.y = double (mid.y + dx);       
                       p3.x = double (mid.x + dy);
                       p3.y = double (mid.y - dx);   
                       if (bsearch (p2) && bsearch (p3)) ++ BEST;    
                   }
               }
          printf ("%d", int (BEST >> 1));     
      }

      int main ()
      {
          freopen (FIN, "r", stdin);
          freopen (FOUT, "w", stdout);
          
          scanf ("%d", &N);
          for (i = 1; i <= N; ++i)
            scanf ("%llf %llf", &A[i].x, &A[i].y);
            
          sort (1, N);
          
          solve ();          
          
          return 0;
      }