Cod sursa(job #1633777)

Utilizator antanaAntonia Boca antana Data 6 martie 2016 12:48:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include<algorithm>
#define MAX 800
#define MAXL 30000
using namespace std;
int v[MAX+1], nrtri;
inline int caut(int st, int dr, int sum)
{
    int mij, c=st;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=sum&&v[mij+1]>sum)
            return mij;
        if(v[mij]<=sum)
            st=mij+1;
        else dr=mij-1;
    }
    return c-1;
}
int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int n, i, j;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    sort(v+1, v+n+1);
    v[n+1]=3*MAXL;
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<n;j++)
            nrtri+=caut(j+1, n, v[i]+v[j])-j;
    printf("%d", nrtri);
    return 0;
}