Cod sursa(job #1546124)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 7 decembrie 2015 18:41:50
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<iostream>
#include<algorithm>
#include<fstream>
#include<cmath>
#define nmax 1009

/// complexitate N^2 * logN

using namespace std;

ifstream fin ("patrate3.in");
ofstream fout ("patrate3.out");

struct coord{
   float x, y;
};

coord a[nmax];
int n, cnt;

inline bool cmp(const coord nr1, const coord nr2)
{
   if (nr1.x == nr2.x) return (nr1.y < nr2.y);
   return (nr1.x < nr2.x);
};

void Citire()
{
  fin >> n;
  for (int i=1; i<=n; i++)
     fin >> a[i].x >> a[i].y;
}

void Sortare()
{
  sort(a+1, a+n+1, cmp);
}

void Construieste(float x0, float y0, float x1, float y1, float &x2, float &y2, float &x3, float &y3)
{
   float xm, ym, dx, dy;
   xm = (x0 + x1) / 2;
   ym = (y0 + y1) / 2;
   dx = fabs(xm - x0);
   dy = fabs(ym - y0);

   if (y0 < y1)
   {
      x2 = xm + dy;
      y2 = ym - dx;
      x3 = xm - dy;
      y3 = ym + dx;
   }

   else /// y0 < y1
   {
      x2 = xm - dy;
      y2 = ym - dx;
      x3 = xm + dy;
      y3 = ym + dx;
   }
}

void Cauta_Binar(float x, float y)
{
   int st, dr, gasit, m;
   st = 1; dr = n; gasit = 0;

   while (st <= dr && gasit == 0)
   {
      m = (st + dr)/2;
      if (a[m].x == x && a[m].y == y) gasit = 1;
      else if (a[m].x == x && a[m].y < y) st = m + 1;
      else if (a[m].x == x && a[m].y > y) dr = m - 1;
      else if (a[m].x < x) st = m + 1;
      else                 dr = m - 1;
   }
   /// caut binar si cresc cnt daca gasesc in vector

   if (gasit == 1) cnt++;
}

void Rezolva()
{
   int i, j, poz;
   float x0, y0, x1, y1, x2, y2, x3, y3;

   for (i=1; i<n; i++)
   {
     for (j=i+1; j<=n; j++)
      {
         /// am (x0, y0) si (x1, y1), imi construiesc (x2, y2), (x3, y3)
         x0 = a[i].x; y0 = a[i].y;
         x1 = a[j].x; y1 = a[j].y;
         Construieste(x0, y0, x1, y1, x2, y2, x3, y3);
         Cauta_Binar(x2, y2);
         Cauta_Binar(x3, y3);
      }
   }

   fout << cnt << "\n";
}

int main ()
{
  Citire();
  Sortare();
  Rezolva();
  fin.close();
  fout.close();
  return 0;
}