Cod sursa(job #2755529)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 27 mai 2021 16:30:48
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>


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

struct point{
    int x,y;
}V[1005];

int N;

bool cmp(point A, point B){
    return A.x < B.x || (A.x == B.x && A.y < B.y);
}

bool binS(point A){
    int l = 1; 
    int r = N;;
    int m;

    while(l <= r){
        m = (l+r) / 2;
        
        // we found the point we're looking for
        if(V[m].x == A.x && V[m].y == A.y){
            return 1;
        }

        if(cmp(V[m], A)){
            l = m + 1;
        }
        else{
            r = m-1;
        }
    }
    
    // the point we are looking for doesn't exist
    return 0;
}




int main(){
    fin >> N;

// no of squares
    int sol = 0;
    double X, Y;

    for(int i = 1; i <= N; i++){
        fin >> X >> Y;

        V[i].x = round(X * 10000);
        V[i].y = round(Y * 10000);
    }

    sort(V+1, V + N + 1, cmp);

    point mid; 
    int rx;
    int ry;

    point B, D;

    // for every two points we search the other ones to form a square
    for(int i = 1; i < N; i++){
        for(int j = i + 1; j <= N; j++){

            // square : A B C D
            // A = V[i] C = V[j]  

            mid.x = (V[i].x + V[j].x) / 2;
            mid.y = (V[i].y + V[j].y) / 2;

            rx = mid.x - V[i].x;
            ry = mid.y - V[i].y;

            B.x = mid.x - ry;
            B.y = mid.y + rx;

            D.x = mid.x + ry;
            D.y = mid.y - rx;

            if(binS(B) && binS(D)){
                sol++;
            }
            
        }
    }

    // we ll count every square 2 times
    fout << sol / 2;

    return 0;

}