Cod sursa(job #2310434)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 31 decembrie 2018 16:27:24
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <algorithm>
#include <fstream>
#define nmax 1001

using namespace std;

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

const double VAL=0.0001;

struct punct
{ double x,y;
};

///date de intrare
punct v[nmax];
int n;
///date de iesiere
int nr_patrate;

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

}
bool cmp(punct A,punct B) ///functia 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_Puncte(punct A) ///cautarea unui punct in vectorul de puncte
{
  int st=1;
  int dr=n;
  int gasit=0;
  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 i,j;
    fin>>n;
    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(A.x,mij.x);
             double dy=mod(A.y,mij.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_Puncte(C)==1 && Cautare_Binara_Puncte(D)==1)
               nr_patrate++;
        }

    fout<<nr_patrate/2;
    return 0;
}