Cod sursa(job #2587806)

Utilizator VladTZYVlad Tiganila VladTZY Data 23 martie 2020 16:20:29
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <algorithm>
#include <stdio.h>

#define NMAX 1005

using namespace std;

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

int n, rez;

const double marja = 1e-5;
struct hh{
    double x, y;
};
hh v[NMAX];

int egal(double a, double b)
{
    double verf = a - b;

    if(verf > -marja && verf < +marja)
        return 1;

    return 0;
}

bool cautaBinar(hh x)
{
    int st = 1, dr = n, mij = 0;
    double fx = x.x, fy = x.y;

    while(st <= dr)
    {
        mij = (st + dr) / 2;

        if(egal(fx, v[mij].x))
        {
            if(egal(fy, v[mij].y))
                return 1;
            if(fy < v[mij].y)
            {
                dr = mij - 1;
                continue;
            }
            else
            {
                st = mij + 1;
                continue;
            }
        }

        if(fx < v[mij].x)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return 0;
}

int patrat(int i, int j)
{
    hh delta, a, b;

    delta.x = (v[i].x + v[j].x) / 2;
    delta.y = (v[i].y + v[j].y) / 2;

    a.x = delta.x - v[j].y + delta.y;
    a.y = delta.y + v[j].x - delta.x;

    b.x = delta.x + v[j].y - delta.y;
    b.y = delta.y - v[j].x + delta.x;

    //g << a.x << " " << a.y << "  " << b.x << " " << b.y << "\n";

    if(cautaBinar(b) && cautaBinar(a))
        return 1;
    return 0;
}

int cmp(hh a, hh b)
{
    if(a.x < b.x)
        return 1;
    if(a.x == b.x && a.y < b.y)
        return 1;
    return 0;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + 1 + n, cmp);

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(patrat(i, j))
                rez += 1;
        }
    }

    g << rez / 2;
    return 0;
}