Cod sursa(job #2469804)

Utilizator rchiteaIRCHIT rchitea Data 8 octombrie 2019 00:03:59
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n, tr[1000], cnt;

    FILE *f=fopen("nrtri.in","r");
    FILE *g=fopen("nrtri.out","w");
void citire()
{
    fscanf(f, "%d", &n);
    for(int i=1; i<=n; i++)
        fscanf(f, "%d", &tr[i]);
    sort(tr+1, tr+n+1);
}

bool verif(int a, int b, int c)
{
    if(a+b>=c && a+c>=b && b+c>=a)
    {
        return true;
    }
    return false;
}

int cautbin(int x, int y)
{
    int st=y+1;
    int dr=n;
    int rez=-1;
    while(st<=dr)
    {
        int mij = (st + dr) / 2;
        if(verif(tr[x], tr[y], tr[mij]))
        {
            rez=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return rez;
}

void preluc()
{
    for(int i=1; i<=n-3; i++)
        for(int j=i+1; j<=n-2; j++)
        {
            int nr=cautbin(i, j);
            if(nr!=-1)
                cnt+=nr-j+1;
        }
    fprintf(g, "%d", cnt);
}

int main()
{
    citire();
    preluc();
    return 0;
}