Cod sursa(job #2075733)

Utilizator pionierul22aNa LiZa pionierul22 Data 25 noiembrie 2017 17:13:48
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[801],i,j,nr;

int triunghi(int i, int j, int m)
{
    if(v[m]<=v[i]+v[j] && v[i]<=v[m]+v[j] && v[j]<=v[i]+v[m])
        return 1;
    return 0;
}

void cautare()
{
    int p=1;
    int u=n;
    while(p<=n)
    {
        int m=(p+u)/2;

        if((triunghi(i,j,m)==1 && v[m+1]>v[i]+v[j])||(m==n && triunghi(i,j,m)==1)&& m!=i && m!=j)
        {
            nr++;
            return;
        }
        else
            if(v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j])
            p=m+1;
        else
            u=m-1;
    }
    return;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];

    for(i=1;i<=n;i++)
        for(j=i+1;j<n;j++)
            cautare();
    fout<<nr;

    return 0;
}