Cod sursa(job #2155610)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 7 martie 2018 22:50:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
#include <stdlib.h>
 
#define MAXN 800
 
int n, result;
int v[MAXN];
 
void read()
{
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&v[i]);
    }
}
 
void print()
{
    printf("%d\n",result);
}
 
int cmp (const void *a, const void *b)
{
    return *((int *) a) - *((int *) b);
}
 
void compute()
{
    qsort(v,n,sizeof(int),cmp);
    for (int k = n - 1; k > 1; --k) {
        int i = 0, j = k - 1;
        while (i < j) {
            int sum = v[i] + v[j];
            if (sum >= v[k]) {
                result += j - i;
                --j;
            } else {
                ++i;
            }
        }
    }
}
 
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    read();
    compute();
    print();
    return 0;
}