Cod sursa(job #61333)

Utilizator RazvanSSavu Razvan RazvanS Data 18 mai 2007 21:04:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#define MAXN 800

using namespace std;

int n;
int V[MAXN];
int r;


int main( void )
    {
     freopen("nrtri.in", "r", stdin);
     scanf("%d\n", &n);
     int i;
     for(i=0; i<n; ++i)
         scanf("%d ", &V[i]);
         
     sort(V, V+n);
     int j;
     int a, b, m, t;
     for(i=0;i<=n-3;++i)
         for(j=i+1;j<=n-2;++j)
            {t=V[i]+V[j];
             if(t>=V[j+1]) if(j==n-2) r++;
                                       else if(t>=V[n-1]) r+=n-j-1;
                                                 else {
                                                       a=j+1; b=n-1;
                                                       while(a+1<b)
                                                          {
                                                           m=(a+b)/2;
                                                           if(t<V[m]) b=m;
                                                             else a=m;
                                                           }
                                                       r+=a-j;
                                                       }
             }
             
      freopen("nrtri.out", "w", stdout);
      printf("%d\n", r);
      
      return 0;
      }