Cod sursa(job #2075626)

Utilizator alexge50alexX AleX alexge50 Data 25 noiembrie 2017 16:08:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
#include <assert.h>

//#define DEBUG

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 && (v[i] + v[j] >= v[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);

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

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

#ifdef DEBUG
    printf("testing...\n");
    int n_tri_test = 0;
    for(int i = 1; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            for(int k = j + 1; k <= n; k++)
                n_tri_test += static_cast<int>(check_triangle(i, j, k));
    printf("%d\n%d\n", n_triangles, n_tri_test);
    assert(n_tri_test == n_triangles);
#endif

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

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