Cod sursa(job #3231640)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 27 mai 2024 14:52:50
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream f ("patrate3.in");
ofstream g ("patrate3.out");

const int NMAX = 1000;
int n, sol;

struct punct {
    int x, y;
};

punct v[NMAX+1], A, B, C, D, O;

bool cmp (punct a, punct b) {
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool cautbin(punct P) {
    int p  = 1, u = n;
    while (p <= u) {
        int m = (p+u)/2;
        if (v[m].x == P.x) {
            if (v[m].y < P.y)
                p = m+1;
            else if (v[m].y > P.y)
                u = m-1;
            else
                return 1;
        } else if (v[m].x > P.x)
            u = m-1;
        else
            p = m+1;
    }
    return 0;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++) {
        double x, y;
        f >> x >> y;
        v[i] = {round(x*10000), round(y*10000)};
    }
    sort (v+1, v+n+1, cmp);
    for (int i=1; i<n; i++)
        for (int j=i+1; j<=n; j++) {
            // Diagonala patratului
            A = v[i];
            C = v[j];
            // Mijlocul patratului
            O = {(A.x+C.x)/2, (A.y+C.y)/2};
            double dX = O.x - A.x,
                   dY = O.y - A.y;
            B = {O.x-dY, O.y+dX};
            D = {O.x+dY, O.y-dX};
            if (cautbin(B) && cautbin(D))
                sol++;
        }
    g << sol/2;
    f.close();
    g.close();
    return 0;
}