Cod sursa(job #1612183)

Utilizator PraetorGrigorosoaia Florin Praetor Data 24 februarie 2016 19:01:22
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#define NRMB 801 // numarul maxim de betisoare
#define S3 90001

using namespace std;

FILE*in;
ofstream out("nrtri.out");

int nr_betisoare;
int lungime[NRMB];
int TR[S3];
int solution;

void read()
{
    in=fopen("nrtri.in", "r");

    fscanf(in, "%d", &nr_betisoare);
    for (int i=1; i<=nr_betisoare; i++)
    {
        fscanf(in, "%d", &lungime[i]);

        TR[lungime[i]]++;
    }
}

void build_sume()
{
    for (int i=3; i<=S3; i++)
        TR[i]+=TR[i-1];
}

void build_solution()
{
    for (int i=1; i<nr_betisoare; i++)
        for (int j=i+2; j<=nr_betisoare; j++)
        {
            int DIF=abs(lungime[i]-lungime[j]);

            if (DIF)
                solution+=(TR[lungime[i]+lungime[j]]-TR[DIF-1]);
            else
                solution+=TR[lungime[i]+lungime[j]];

            if (lungime[i] >= DIF)
                solution--;
            if (lungime[j] >= DIF)
                solution--;
        }

    solution/=3;
}

void solve()
{
    build_sume();
    build_solution();
}

void show()
{
    out<<solution;
}

int main()
{
    read();
    solve();
    show();

    return 0;
}