Cod sursa(job #2198614)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 24 aprilie 2018 20:02:19
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stdlib.h>
#define NMAX 1501

using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
vector < double > Distance;
int ans;
struct Point{
    double x, y;
}a[NMAX];
int N;
int FindDistance(int i, int j)
{
    double d1=a[i].x-a[j].x;
    double d2=a[i].y-a[j].y;
    return sqrt(d1*d1 + d2*d2);
}
int cautbinar(int st, int dr, int val)
{
    int mij;
    int poz=-2;
    while(st <= dr)
    {
        int mij=(st+dr)/2;
        if(Distance[mij]==val)
            {
                poz=mij;
             st=mij+1;
            }
        else if(Distance[mij] < val)
            st=mij+1;
        else dr=mij-1;
    }
    return poz;
}
int main()
{
    fin>>N;
    for(int i = 1; i <=  N; i++)
    {
        fin>>a[i].x>>a[i].y;
        for(int j = 1; j < i ; j++)
          {
              double c= FindDistance(i,j);
               Distance.push_back(c);
          }
    }
    sort(Distance.begin(),Distance.end());
    for(int i =0 ; i <= N ; i ++)
        for(int j =0 ; j<= N; j++)
    {
        double Dist=Distance[i]+Distance[j];
       int nr=cautbinar(j+1,N,Dist);
         if( nr!=-2 )
        ans+=nr-j; ///intervalul de valori bune;
    }
 fout<<ans;

    return 0;
}