Cod sursa(job #288277)

Utilizator pedobearBacauanu Vlad pedobear Data 25 martie 2009 17:55:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int v[810];
int i,j,n,st,dr,mid,sol,nr;

int main ()
{
    freopen ("nrtri.in","r",stdin);
    freopen ("nrtri.out","w",stdout);
    
    scanf ("%d",&n);
    for (i=1;i<=n;i++) scanf ("%d",&v[i]);
    
    sort(v+1,v+n+1);
    
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            st=j+1; dr=n; sol=j;
            while (st<=dr){
                  mid=(st+dr)/2;
                  if (v[i]+v[j]>=v[mid]) {
                                         st=mid+1;
                                         sol=mid;
                                         }
                  else dr=mid-1;
                  }
            nr=nr+sol-j;
            }
        }
        
    printf ("%d",nr);
    
    return 0;
}