Cod sursa(job #2064388)

Utilizator gundorfMoldovan George gundorf Data 12 noiembrie 2017 12:00:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#define Nmax 2500
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[Nmax];

int Cautare_Binara (int s,int d,int a,int b)
{
    int i=s,j=d,mij;
    while (i<=j)
    {
        mij=(i+j)/2;
        if (v[mij]<=a+b) return mij;
        else if (v[mij]>a+b) j=mij-1;
    }
    return -1;
}

int main()
{int i,numaratoare=0,j;
fin>>n;
for (i=1;i<=n;i++)
    fin>>v[i];
    sort(v+1,v+n+1);
    for (i=1;i<=n-2;i++)
        for (j=i+1;j<=n-1;j++)
    {
        int p=Cautare_Binara(j+1,n,v[i],v[j]);
        if (p!=-1)
        { //fout<<v[i]<<" "<<v[j]<<" "<<v[p]<<"\n";
            while (v[p+1]<=v[i]+v[j]&&p<n) p++;
            numaratoare+=p-j;
        }
    }
    fout<<numaratoare;
    return 0;
}