Cod sursa(job #2804041)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 20 noiembrie 2021 19:09:30
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <algorithm>
#include <fstream>

using namespace std;

/*ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
*/

ifstream fin("nr2.in");
ofstream fout("nr2.out");

int n,v[805],nrtri;

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

    sort(v+1,v+n+1);

    v[n+1]=60000;
    for(int i=1;i<n-1;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            int p=upper_bound(v+j+1,v+n+1,v[i]+v[j])-v;
            if(v[p]<=v[i]+v[j]) nrtri+=p-j;
            else nrtri+=p-j-1;
        }
    }

    fout << nrtri;
    return 0;
}