Cod sursa(job #2314528)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 8 ianuarie 2019 17:33:50
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb

#include <fstream>
#include <iostream>
#include <math.h>
#include <cmath>
#include <algorithm>
#define marja 0.0001 //deoarece coordonatele punctelor date au\
//4 zecimale, alegem valoarea 0.0001 pentru marja
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
typedef struct{
    double x, y;
}punct;//aceasta structura memoreaza coordanetele unui punct in plan
punct v[1001];
int N,i,j,Counter;
int modul(int a,int b) //este calculat modulul diferentei (a-b)
{
    if(a-b>=0)
    {
        return (a-b);
    }
    else
    {
        return (-1)*(a-b);
    }
}
void citire()
{
    fin>>N;// se citeste N-numarul de puncte
    for(i=1;i<=N;i++)
    {
        fin>>v[i].x>>v[i].y; // se citesc coordonatele celor N puncte
    }
}
int comparare(punct A,punct B)
{
    /*
    sortam crescator 
    */
    if(A.x<B.x)
    {
        return 1;
    }
    else if(A.x==B.x && A.y<B.y) //cazul in care abscisa coincide
    {
        return 1;
    }
    else
    {
    return 0;
    }
}
int cautare(punct A)
{
    double p,q;
    int st=1,dr=N,mij;
    /*
    aceasta este o cautare binara particularizata
    in care trebuie sa determinamn daca putem gasi un patrat ce poate fi format
    */
    while(st<=dr)
    {
        mij=(st+dr)/2;
        p=A.x-v[mij].x;
        q=A.y-v[mij].y;
        if(abs(p)<marja && abs(q)<marja) //daca rezultatul celor 2 diferente
        { //este mai mic decat marja, atunci putem avea patrat
            return 1;
        }
        if(abs(p)<marja)//daca prima diferenta e mai mica decat marha
        {
            if(A.y<v[mij].y) //daca coltul are ordonata mai mica decat punctul v[mij]
            {
                dr=mij-1; 
            }
            else
            {
                st=mij+1;
            }
        }
        else
        {
            if(A.x<v[mij].x)//daca coltul are abscisa mai mica
            {
                dr=mij-1;
            }
            else
            {
                st=mij+1;
            }
        }
    }
    return 0;
}

int numarare_patrate()
{
    for(i=1;i<=N-1;i++)
        for(j=i+1;j<=N;j++)
    {
        punct A,B,mij;
        mij.x=(v[i].x+v[j].x)/2.0;
        mij.y=(v[i].y+v[j].y)/2.0;
        //punctul mij reprezinta mijlocul
        A.x=mij.x-v[j].y+mij.y;
        A.y=mij.y+v[j].x-mij.x;
        //A devine coltul dreapta jos al patratului
        B.x=mij.x+v[j].y-mij.y;
        B.y=mij.y-v[j].x+mij.x;
        //B devine coltul stanga sus al patratului
        if(cautare(A) && cautare(B))//daca a fost gasit un patrat pentru A si B
        {
            Counter++;//il crestem pe Counter
        }
    }
    return Counter/2;//il returnam drept Counter/2 deoarece avem de doua ori mai multe patrate
}

int main()
{
    citire();
    sort(v+1,v+N+1,comparare);//vectorul de puncte este sortat
    //in mod crescator
    fout<<numarare_patrate();//apelam functia numarare_patrate();
    fin.close();
    fout.close();
    return 0;
}