Cod sursa(job #1463108)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 20 iulie 2015 02:59:12
Problema Triang Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
int N;
pair <double,double> Array[1505];
double Distance[1505][1505];
const double eps = 0.001;
pair <double,int> D[1505][1505];
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>Array[i].first>>Array[i].second;
}
inline double Dist(pair<double,double> a,pair <double,double> b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

void precalcDistance()
{
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
            D[i][j].first=Dist(Array[i],Array[j]),D[i][j].second=j;
    for(int i=1;i<=N;i++)
        sort(D[i]+1,D[i]+N+1);
}
pair <double,double> binSearch(int point,double Dist)
{
    int left=1,right=N,mid,sol=0;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(D[point][mid].first-Dist<-eps)
        {
            left=mid+1;
            continue;
        }
        if(D[point][mid].first-Dist>eps)
        {
            right=mid-1;
            continue;
        }
        sol=mid;
        break;
    }
    if(sol==0)
        return make_pair(-1000000000.,-1000000000.);
    else
        return Array[D[point][sol].second];
}
inline double mod(double x)
{
    return max(x,-x);
}
void Solve()
{
    int ans=0;
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
        {
            double Distance=Dist(Array[i],Array[j]);
            pair<double,double> x=binSearch(j,Distance);
            if(x!=make_pair(-1000000000.,-1000000000.) && mod(Dist(Array[i],x)-Distance)<=eps)
                ++ans;
        }
    g<<ans<<"\n";
}
int main()
{
    Read();
    precalcDistance();
    Solve();
    return 0;
}