Cod sursa(job #2075524)

Utilizator alexge50alexX AleX alexge50 Data 25 noiembrie 2017 15:13:07
Problema Numarare triunghiuri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <algorithm>

const int MAX_N = 800;

int v[MAX_N + 1];

bool check_triangle(int i, int j, int k)
{
    bool a, b, c;
    a = v[i] <= v[k] + v[j];
    b = v[j] <= v[i] + v[k];
    c = v[k] <= v[j] + v[i];
    return a && b && c;
}

bool compare(const int& lhs, const int& rhs)
{
    return lhs > rhs;
}

int binsearch(int n, int i, int j)
{
    int step = 1 << 10;
    int r = 0;

    while(step != 0)
    {
        if(r + step <= n && check_triangle(i, j, r + step))
            r += step;
        step /= 2;
    }

    return r;
}

int main()
{
    FILE *fin = fopen("nrtri.in", "r"),
         *fout = fopen("nrtri.out", "w");
    int n;
    int n_triangles;

    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);

    std::sort(v + 1, v + n + 1, compare);

    n_triangles = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int k = binsearch(n, i, j);
            int x = static_cast<int>(i <= k) + static_cast<int>(j <= k);

            if(j < k)
                n_triangles += k - j;
        }
    }

    fprintf(fout, "%d", n_triangles);

    fclose(fin);
    fclose(fout);
    return 0;
}