Cod sursa(job #2310351)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 31 decembrie 2018 12:48:42
Problema Patrate 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <algorithm>
#define nmax 1001

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

struct punct
{ double x,y;
};

const double VAL=0.0001;
///date de intrare
int n;
punct v[nmax];
///date de iesire
int nr_patrate;

double mod(double x,double y)///functia modul
{ if(x > y) return (x-y);
  else return (y-x);
}

int cmp(punct A,punct B) ///functie de comparare
{
    if(A.x == B.x)
      { if(A.y <= B.y) return 1;
        else return 0;
      }
    else
      if(A.x <= B.x) return 1;
      else return 0;
}

int Cautare_Binara_Punct(punct A)
{
  int gasit=0;
  int st=1,dr=n;
  while(st<=dr && gasit==0)
       {
         int mij=(st+dr)/2;
         if(mod(v[mij].x , A.x) < VAL &&
            mod(v[mij].y , A.y) < VAL) gasit=1;
         else
            if(mod(v[mij].x , A.x) < VAL)
              {
                if(A.y<v[mij].y) dr=mij-1;
                else st=mij+1;
              }
            else
               {
                 if(A.x<v[mij].x) dr=mij-1;
                 else st=mij+1;
               }
       }

  return gasit;
}

int main()
{
  int n;
  fin>>n;
  int i,j;
  for(i = 1; i <= n; i++)
       fin>>v[i].x>>v[i].y;

  ///sortam crescator vectorul de puncte(dupa abscise, iar pt abscise egale dupa ordonate)
  sort(v+1,v+n+1,cmp);

  ///cautam nr de patrate
  for(i = 1; i <= n; i++)
       for(j = i+1; j <= n; j++)
           {
             ///luam 2 puncte din vectorul de puncte si presupunem ca formeaza o diagonala
             punct A,B;
             A = v[i];
             B = v[j];

             ///aflam celelalte 2 puncte ale patratului
             punct C,D;
             punct mij;///mijlocul patratului
             mij.x = (A.x + B.x)/2;
             mij.y = (A.y + B.y)/2;
             double dx = mod(mij.x , A.x);
             double dy = mod(mij.y , A.y);
             if(A.y < B.y)
               {
                   C.x = mij.x + dy;
                   C.y = mij.y - dx;
                   D.x = mij.x - dy;
                   D.y = mij.y + dx;
               }
             else
               {
                   C.x = mij.x - dy;
                   C.y = mij.y - dx;
                   D.x = mij.x + dy;
                   D.y = mij.y + dx;
               }

             ///cautam binar cele 2 puncte aflate, iar daca sunt gasite inseamna ca formeaza un patrat cu cele 2 puncte alese initial
             if(Cautare_Binara_Punct(C)==1 && Cautare_Binara_Punct(D)==1)
                     nr_patrate++;
           }
  fout<<nr_patrate/2;
    return 0;
}