Cod sursa(job #2491666)

Utilizator victorv88Veltan Victor victorv88 Data 12 noiembrie 2019 22:04:59
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

const double eps=0.001;

int n;
pair<double,double>puncte[1505];

double calculare_distanta(pair<double,double>a, pair<double,double>b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}

double absol(double a)
{
    if (a<0)
        return -a;
    return a;
}

int cautare_binara(pair<double,double>a, pair<double,double>b, int st, int dr)
{
    double distanta=calculare_distanta(a,b);

    int mij;
    double distanta_punct;
    double distanta_punct2;

    while (st<=dr)
    {
        mij=(st+dr)/2;
        distanta_punct=calculare_distanta(a,puncte[mij]);
        distanta_punct2=calculare_distanta(b,puncte[mij]);
        if (absol(distanta-distanta_punct)<=eps && absol(distanta-distanta_punct2)<=eps)
        {
            return 1;
        }
        else if (distanta<distanta_punct)
            dr=mij-1;
        else
            st=mij+1;

    }
    return 0;

}

void solve()
{
    int rez=0;

    for (int i=1; i<n; ++i)
    {
        for (int j=i+1; j<=n; ++j)
        {
            if (cautare_binara(puncte[i],puncte[j],j+1,n))
                ++rez;
        }
    }
    g << rez;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        f >> puncte[i].first >>puncte[i].second;
    }
    sort(puncte+1,puncte+n+1);

    solve();
    return 0;
}