Cod sursa(job #2156761)

Utilizator topala.andreiTopala Andrei topala.andrei Data 8 martie 2018 23:36:52
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
const int maxn = 1002;
const double EPS = 1e-12;
struct point
{
    double x,y;
};
point P[maxn];
int N,ans;

bool D_Egal(double A, double B)
{
    return abs (A - B) < EPS;
}
bool cmp(point A, point B)
{
    if (D_Egal(A.x, B.x) == 1)
        return A.y < B.y;
    return A.x < B.x;
}
int Binary_Search(point A)
{
    int left=1, right=N, mid;

    while (left <= right)
    {
        mid = (left + right)/2;

        if (D_Egal(P[mid].x, A.x) == 1 && D_Egal(P[mid].y, A.y) == 1) return 1;


        if (D_Egal(P[mid].x, A.x) == 1)
        {
            if (P[mid].y < A.y)
                left = mid + 1;
            else
                right = mid - 1;
        }

        else
        {
            if (P[mid].x < A.x)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }

    return 0;
}
void Solve()
{
    for (int i = 1; i < N; i++)
        for (int j = i+1; j <= N; j++)
        {
            point M, A, B;

            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 (Binary_Search(A) == 1 && Binary_Search(B) == 1)
                ans++;
        }
    ans/=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);

    Solve();
    g<<ans;

    return 0;

}