Cod sursa(job #89119)

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

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

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;
          */
          
          ifstream fin("patrate3.in");
          ofstream fout("patrate3.out");

          fin>>N;
          for(i = 1;i<=N;i++)
            fin>>A[i].x>>A[i].y;
            
          sort(1,N);
          solve();
          
          int sol = BEST>>1;
          fout<<sol<<"\n";
          
          return 0;

      }