Cod sursa(job #2236615)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 august 2018 00:24:58
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define eps 0.00001
 
using namespace std;
 
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
struct point{
    double x, y;
}P[1005];

int N,nr;
int SquaresCount;

int cmp(point A, point B){
    if(A.x < B.x)
        return 1;
    if(A.x == B.x && A.y < B.y)
        return 1;
    return 0;
}

int exists(point A){


    int left = 1, right = N, mid;

    while(left <= right){
        mid = (left + right) / 2;
        if(abs(A.x - P[mid].x) < eps && abs(A.y - P[mid].y) < eps){
            return 1;
        }
        if(abs(A.x - P[mid].x) < eps){
            if(A.y < P[mid].y)
                right = mid - 1;
            else
                left = mid + 1;
        }else{
            if(A.x < P[mid].x)
                right = mid - 1;
            else
                left = mid + 1;
        }
    }

    return 0;
}

int main(){
    fin>>N;
    
    for(int i = 1; i <= N; i ++)
        fin >> P[i].x >> P[i].y;

    sort(P + 1, P + N + 1, cmp);
    
    for(int i = 1; i < N; i ++)
        for(int j = i + 1; j <= N; j ++){

            point firstPoint, secondPoint;

            point mid;
            mid.x = (P[i].x + P[j].x) / 2.0;
            mid.y = (P[i].y + P[j].y) / 2.0;

            firstPoint.x = mid.x - P[j].y + mid.y;
            firstPoint.y = mid.y + P[j].x - mid.x;

            secondPoint.x = mid.x + P[j].y - mid.y;
            secondPoint.y = mid.y - P[j].x + mid.x;

            if(exists(firstPoint) && exists(secondPoint))
                SquaresCount ++;
        }

    fout << SquaresCount / 2 << "\n";
    
}