Cod sursa(job #3185612)

Utilizator devieiDevid Mecu deviei Data 19 decembrie 2023 19:02:57
Problema Numarare triunghiuri Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>
#define Nr 802
int v[Nr];

int compara(const void * a, const void *b) {
    return ( *(int *)b - *(int *)a );
}

int main(int argc, char **argv) {
   freopen("nrtri.in", "r", stdin);
   freopen("nrtri.out", "w", stdout);
    int N = 0, i = 0, j = 0, mijloc = 0;
    scanf("%d", &N); 
    for(i = 1; i <= N; i++){
        scanf("%d", &v[i]);
    }
    qsort(v, N, sizeof(int), compara);
    int st, dr, aux, nr = 0;
    for(i = 1; i <= N; i++){
        for(j = i + 1; j <= N; j++){
            st = j;
            dr = N;
            aux = j;
            while(st <= dr) {
                mijloc = (st + dr) / 2;
                if(v[mijloc] <= v[i] + v[j]) {
                    st = mijloc + 1;
                    aux = mijloc;
                }
                else
                {
                    dr = mijloc - 1;
                }
            }
            nr += aux-j;
        }
    }
    printf("%d", nr);
    return 0;
}