Cod sursa(job #2470295)

Utilizator ilincaspIlinca Sfrijan-Penciu ilincasp Data 8 octombrie 2019 23:06:24
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n, tr[3001], 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+1+n);
}

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-2; i++)
        for(int j=i+1; j<=n-1; j++)
        {
            int nr=cautbin(i, j);
            if(nr!=-1)
                cnt+=nr-j;
        }
    fprintf(g, "%d", cnt);
}

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