Cod sursa(job #1358024)

Utilizator papinubPapa Victor papinub Data 24 februarie 2015 12:17:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
# include <fstream>
# include <algorithm>
# define DIM 810
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[DIM],i,j,n,poz1,poz2,nr;
int caut(int p,int u,int a,int b)
{
    int mij,ini;
    ini=p;
    while (p<u)
    {
        mij=(p+u)/2;
        if (a+b>v[mij]) u=mij;
        else p=mij+1;
    }
    return p-ini+1;
}
int main()
{
    in>>n;
    for (i=1;i<=n;i++) in>>v[i];
    sort(v+1,v+n+1);
    for (i=1;i<=n-2;i++)
    {
        for (j=i+1;j<=n-1;j++)
        {
            if (j!=n-1)
            nr+=caut(j+1,n,v[i],v[j]);
            else if (v[i]+v[j]>=v[n] && v[i]+v[n]>=v[j] && v[j]+v[n]>=v[i]) nr++;
        }
    }
    out<<nr;
    return 0;
}