Cod sursa(job #2064812)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 12 noiembrie 2017 20:43:28
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>
int n,a[801],poz,s;
int Pivotare(int st,int dr)
{ int aux,i,j,p=(st+rand()%(dr-st+1)+st+rand()%(dr-st+1)+st+rand()%(dr-st+1))/3;
    //swap(a[p],a[dr]);
    aux=a[p];
    a[p]=a[dr];
    a[dr]=aux;
    i=st-1;
    for(j=st;j<=dr;j++)
     if(a[j]<a[dr])
      { i++;
          //swap(a[i],a[j]);
          aux=a[i];a[i]=a[j];a[j]=aux;
      }
      //swap(a[i+1],a[dr]);
      aux=a[i+1];a[i+1]=a[dr];a[dr]=aux;
      return i+1;
}
void QuickSort(int st,int dr)
{ if(st<dr)
  { int p=Pivotare(st,dr);
    QuickSort(st,p-1);
    QuickSort(p+1,dr);
  }
}
int Cautbin(int p,int x)
{ int st=p,dr=n,mij;
     while(st<=dr)
     { mij=st+(dr-st)/2;
         if(a[mij]==x&&a[mij+1]!=x) return mij;
         else if(a[mij]==x&&a[mij+1]==x) ++st;
         else if(a[mij]<x) st=mij+1;
         else if(a[mij]>x) dr=mij-1;
     }
     if(a[mij]>x) return mij-1;
     if(a[mij]<x) return mij;
}
int main()
{ int i,j;
    FILE *f,*g;
    f=fopen("nrtri.in","r");
    g=fopen("nrtri.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d",a+i);
    QuickSort(1,n);
    for(i=1;i<=n-2;++i)
     for(j=i+1;j<=n-1;++j)
      { poz=Cautbin(j+1,a[i]+a[j]);
         s+=poz-(j+1)+1;
      }
    fprintf(g,"%d",s);
    return 0;
}