Cod sursa(job #3185642)

Utilizator devieiDevid Mecu deviei Data 19 decembrie 2023 19:38:30
Problema Numarare triunghiuri Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#include <stdlib.h>
#define Nr 802
int vector[Nr];
//functia pentru qsort(in mod crescator)
int compara(const void * a, const void *b) {
    return ( *(int *)a - *(int *)b );
}
int main() {
   freopen("nrtri.in", "r", stdin);
   freopen("nrtri.out", "w", stdout);
   int N, i, j, nr = 0;
   scanf("%d", &N); 
    for(i = 1; i <= N; i++){
        scanf("%d", &vector[i]);
    }
    qsort(vector, N, sizeof(int), compara);
    for(i = 1; i <= N; i++){
        for(j = i + 1;j <= N; j++) {
            int st = j;
            int dr = N;
            int verificareTriunghi = j;
            while(st <= dr) {
                int mijloc = (st + dr) / 2;
                if(vector[mijloc] <= vector[i] + vector[j]) {
                    verificareTriunghi = mijloc;
                    st = mijloc + 1;
                }else {
                    dr = mijloc - 1;
                }
            }
            nr += verificareTriunghi-j;
        }
    }
    printf("%d", nr);
    return 0;
}