Cod sursa(job #2147518)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 28 februarie 2018 19:58:53
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#define eps 1e-4

using namespace std;

struct Punct
{
    double x, y;
    bool operator<(const Punct& a) const
    {
        if(abs(x - a.x) < eps)
            return y < a.y;
        return x < a.x;
    }
    bool operator==(const Punct& a) const
    {
        return abs(x - a.x) < eps && abs(y - a.y) < eps;
    }
} v[1010];

int n;

bool cautbin(const Punct& p)
{
    int st = 0, dr = n - 1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] == p)
            return true;
        if(p < v[mij])
            dr = mij - 1;
        else st = mij + 1;
    }
    return false;
}

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    scanf("%d", &n);
    int rez = 0;
    for(int i = 0; i < n; i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v, v + n);
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            Punct a, b, m;
            m.x = (v[i].x + v[j].x) / 2.;
            m.y = (v[i].y + v[j].y) / 2.;
            a.x = m.x - v[j].y + m.y;
            a.y = m.y + v[j].x - m.x;
            b.x = m.x + v[j].y - m.y;
            b.y = m.y - v[j].x + m.x;
            if(cautbin(a) && cautbin(b))
                rez++;
        }
    }
    printf("%d", rez / 2);
    return 0;
}