Cod sursa(job #2770077)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 19 august 2021 12:27:45
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const double EPS = 1e-5;

struct Punct
{
    double x, y;
};

int N;
Punct P[1001];

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

int egal(double a, double b)
{
    double d = a - b;
    if(d < -EPS)return -1;
    if(d > +EPS)return +1;
    return 0;
}

int egal(const Punct &A, const Punct &B)
{
    int ex = egal(A.x, B.x),
        ey = egal(A.y, B.y);
    if(ex == 0) return ey;
    return ex;
}

bool cmp(const Punct &A, const Punct &B)
{
    return egal(A, B) < 0;
}

bool cautbin(const Punct &A)
{
    int st = 1, dr = N;
    while(st <= dr)
    {
        int m = (st + dr) / 2,
            e = egal(P[m], A);
        if(e == 0)
            return 1;
        if(e == 1)
            dr = m - 1;
        else
            st = m + 1;
    }
    return 0;
}

void solve()
{
    Punct M, A, B;
    int nrp = 0;
    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++) ///Punctele P[i] si P[j] formeaza o diagonala
        {
            M.x = (P[i].x + P[j].x) / 2;
            M.y = (P[i].y + P[j].y) / 2;
            A.x = M.x - P[j].y + M.y;
            A.y = M.y + P[j].x - M.x;
            B.x = M.x + P[j].y - M.y;
            B.y = M.y - P[j].x + M.x ;
            if(cautbin(A) && cautbin(B))
                nrp++;
        }
    g << nrp / 2;
}

int main()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        f >> P[i].x >> P[i].y;
    //sort(P + 1, P + N + 1, cmp);
    sort(P + 1, P + N + 1, [](const Punct & A, const Punct & B)
    {
        return egal(A, B) < 0;
    });
    solve();
    return 0;
}