Cod sursa(job #3352614)

Utilizator 33AMTreizecisitrei Am 33AM Data 29 aprilie 2026 14:27:58
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int cb1(int v[], int a, int c, int b)
{
    int m;
    while(a<c)
    {
        m=a+(c-a)/2;
        if(v[m]<=b)
            a=m+1;
        else
            c=m;
    }
    return a;
}
int cb2(int v[], int a, int c, int b)
{
    int m;
    while(a<c)
    {
        m=a+(c-a)/2;
        if(v[m]<b)
            a=m+1;
        else
            c=m;
    }
    return a;
}
int main()
{
    int n, v[801], p, q, nr=0, aux;
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    if(n<3)
        fout<<0;
    else
    {
        for(int i=1; i<=n;i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                if(v[i]>v[j])
                {
                    aux=v[j];
                    v[j]=v[i];
                    v[i]=aux;
                }
            }
        }
        for(int a=1; a<=n; a++)
        {
            for(int c=a+2; c<=n; c++)
            {
                p=cb2(v,a+1,c,v[c]-v[a]);
                if(p<a+1)
                    p=a+1;
                q=cb1(v,a+1,c,v[c]+v[a])-1;
                if(q>c-1)
                    q=c-1;
                if(q>=p)
                    nr=nr+(q-p+1);
            }
        }
    }
    fout<<nr;
}