Cod sursa(job #370487)

Utilizator GotenAmza Catalin Goten Data 1 decembrie 2009 13:49:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream.h>

long nn,n,a[1000],d,s,nr;




void ex(long i,long j)
{
 long aux=a[i];
 a[i]=a[j];
 a[j]=aux;
 }

void qs(long i,long j)
{
 long s=i,d=j,piv=a[(i+j)>>1];
 while(s<=d)
 {
  while(a[s]<piv)s++;
  while(a[d]>piv)d--;
  if(s<=d)
   {
    ex(s,d);
    s++;
    d--;
    }
  }
 if(i<d) qs(i,d);
 if(s<j) qs(s,j);
 }

int main()
{
int i,j,l,r,m;
 ifstream f("nrtri.in");
 ofstream g("nrtri.out");
 f>>n;
 for(i=1;i<=n;i++)f>>a[i];
 qs(1,n);
 for(i=1;i<=n-2;i++)
   {
    j=i+1;
    d=a[j]-a[i];
    s=a[i]+a[j];
    l=j+1;r=n;
    while(l<r)
     {
      m=l+((r-l)>>1);
      if(a[m]<=s)l=m+1;
      else r=m-1;
      }
    while(a[l]>s)l--;
    nn=l;
    l=j+1;r=n;
    while(l<r)
     {
      m=l+((r-l)>>1);
      if(a[m]>=d)r=m;
      else l=m+1;
      }
    while(a[r]<d)r++;
    nn=nn-r+1;
    if(nn>0)nr+=nn;
    }
 g<<nr;
 return 0;
 }