Cod sursa(job #289779)

Utilizator xtremespeedzeal xtreme Data 26 martie 2009 23:21:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<iostream.h>
#include<stdio.h>
#define Nmax 800

int a[Nmax+1],i,j,inc,fin,med;unsigned int s;

int main()
    {freopen("nrtri.in","r",stdin);freopen("nrtri.out","w",stdout);
    scanf("%d\n",&a[0]);
    for(i=1;i<=a[0];i++)
             scanf(" %d",&a[i]);
    for(i=1;i<=a[0]-1;i++)
         for(j=i+1;j<=a[0];j++)
                 if(a[i]>a[j])
                    {med=a[i];a[i]=a[j];a[j]=med;}
    for(i=1;i<=a[0]-2;i++)
           for(j=i+1;j<=a[0]-1;j++)
               {inc=1;fin=a[0];
               med=(inc+fin)/2;
               while(inc<=fin)
                  {if((a[i]+a[j]>=a[med] && a[i]+a[j]<a[med+1]) || (a[i]+a[j]>=a[med] && med==a[0]))
                                     {s+=med-j;break;}
                  else if(a[med]<=a[i]+a[j] && a[med+1]<=a[i]+a[j])
                                    {inc=med+1;med=(inc+fin)/2;}
                  else
                        {fin=med-1;med=(inc+fin)/2;}
                  }
               }    
    printf("%d",s);
    return 0;
    }