Cod sursa(job #2068297)

Utilizator copanelTudor Roman copanel Data 17 noiembrie 2017 15:56:24
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>

#define L 9

int v[801];

int cmp(const void *a, const void *b) {
    int aa = *(int *)a;
    int bb = *(int *)b;
    if (aa < bb)
        return -1;
    else if (aa == bb)
        return 0;
    else
        return +1;
}

int main()
{
    FILE *fin, *fout;
    int n, i;
    int pas, r;
    int a, b, c;
    int nrtri;

    fin = fopen("nrtri.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);

    qsort(v + 1, n, sizeof(int), cmp);

    nrtri = 0;
    for (a = 1; a <= n - 2; a++) {
        for (b = a + 1; b <= n - 1; b++) {
            pas = 1 << L;
            r = 0;
            while (pas != 0) {
                if (r + pas <= n && v[r + pas] <= v[a] + v[b]) {
                        r += pas;
                }
                pas >>= 1;
            }
            if (r > b && v[a] + v[b] >= v[r])
                nrtri++;
        }
    }

    fout = fopen("nrtri.out", "w");
    fprintf(fout, "%d", nrtri);
    fclose(fout);
    return 0;
}