Cod sursa(job #1491955)

Utilizator MirunaMMiruna Mitu MirunaM Data 26 septembrie 2015 18:36:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int v[2005],vc[70005];
int main(){
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
    int j,i,nr=0,n,max1=-1;
scanf("%d",&n);
for(i=1;i<=n;i++){
    scanf("%d",&v[i]);
    vc[v[i]]++;
    if(v[i]>max1)
        max1=v[i];
}
for(i=1;i<=max1;i++)
    vc[i]+=vc[i-1];
sort(v,v+n+1);
for(i=max1+1;i<=v[n]+v[n-1];i++)
    vc[i]=vc[i-1];
for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++){
        nr+=(vc[v[i]+v[j]-1]-vc[v[j]-v[i]]);
        if((v[i]>(v[j]-v[i]))&&(v[i]<(v[i]+v[j])))
            nr--;
        if((v[j]>(v[j]-v[i]))&&(v[j]<(v[i]+v[j])))
            nr--;
    }
printf("%d",nr/3);
return 0;
}