Cod sursa(job #1593075)

Utilizator EpictetStamatin Cristian Epictet Data 8 februarie 2016 11:46:25
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <algorithm>

#define x first
#define y second

using namespace std;

ifstream fin ("patrate3.in");
ofstream fout ("patrate3.out");

long long n, sol;
pair < double, double > V[1010];
pair < double, double > aux;

inline double Modul(double m)
{
    if (m < 0) return -m;
    return m;
}

inline bool compara1 (double a, double b)
{
    if (a <= b + 0.001) return true;
    return false;
}

inline bool compara2 (double a, double b)
{
    if (Modul(a - b) <= 0.001) return true;
    return false;
}

bool Caut_Binar(pair < double, double > elem)
{
    int i = 0;
    for (int lg = 1024; lg; lg >>= 1)
    {
        if (i + lg <= n && compara1(V[i + lg].x, elem.x))
        {
            if (compara2(V[i + lg].x, elem.x))
            {
                if (compara1(V[i + lg].y, elem.y))
                {
                    i += lg;
                }
            }
            else
            {
                i += lg;
            }
        }
    }

    return (compara2(V[i].x, elem.x) && compara2(V[i].y, elem.y));
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i ++)
    {
        fin >> aux.x >> aux.y;
        V[i].x = aux.x * 100000;
        V[i].y = aux.y * 100000;
    }

    sort (V + 1, V + 1 + n);

    for (int i = 1; i <= n; i ++)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            pair < double, double > mij, d, pct1, pct2;
            mij.x = (V[i].x + V[j].x) / 2;
            mij.y = (V[i].y + V[j].y) / 2;
            d.x = Modul(mij.x - V[i].x);
            d.y = Modul(mij.y - V[i].y);

            if (V[i].y < V[j].y)
            {
                pct1.x = mij.x - d.y;
                pct1.y = mij.y + d.x;
                pct2.x = mij.x + d.y;
                pct2.y = mij.y - d.x;
            }
            else
            {
                pct1.x = mij.x - d.y;
                pct1.y = mij.y - d.x;
                pct2.x = mij.x + d.y;
                pct2.y = mij.y + d.x;
            }

            if (Caut_Binar(pct1) && Caut_Binar(pct2)) sol ++;
        }
    }

    fout << sol / 2 << '\n';
    fout.close();
    return 0;
}