Cod sursa(job #2312326)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 4 ianuarie 2019 18:08:32
Problema Patrate 3 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

struct punct {
    int x, y;
};

int n, sol;
punct p[1000], verif1, verif2;

bool cmpX(punct a, punct b) {
    if (a.x < b.x)
        return 1;
    if (a.x > b.x)
        return 0;
    if (a.y < b.y)
        return 1;
    if (a.y > b.y)
        return 0;
    return 0;
}

bool caut_bin(punct v) {
    int st = 0, dr = n - 1, mij, sol = -1;
    while (st <= dr) {
        mij = st + (dr - st) / 2;
        if (p[mij].x == v.x) {
            sol = mij;
            dr = mij - 1;
        }
        else
            if (p[mij].x < v.x)
                st = mij + 1;
            else
                dr = mij - 1;
    }
    if (sol == -1)
        return 0;
    if (p[sol].y == v.y)
        return 1;
    st = sol;
    dr = n - 1;
    while (st <= dr) {
        mij = st + (dr - st) / 2;
        if (p[mij].y == v.y)
            return 1;
        else
            if (p[mij].y < v.y)
                st = mij + 1;
            else
                dr = mij - 1;
    }
    return 0;
}

int main() {
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    scanf("%d", &n);
    double x, y;
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &x, &y);
        p[i].x = round(x * 10000);
        p[i].y = round(y * 10000);
    }
    sort(p, p + n, cmpX);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            verif1.x = (p[i].x + p[j].x + p[j].y - p[i].y) / 2;
            verif1.y = (p[i].y + p[j].y + p[i].x - p[j].x) / 2;
            if (!caut_bin(verif1))
                continue;
            verif2.x = (p[i].x + p[j].x + p[i].y - p[j].y) / 2;
            verif2.y = (p[i].y + p[j].y + p[j].x - p[i].x) / 2;
            if (caut_bin(verif2))
                sol++;
        }
    }
    printf("%d", sol / 2);
    return 0;
}