Cod sursa(job #1023)

Utilizator mika17Mihai Alex Ionescu mika17 Data 12 decembrie 2006 14:08:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#define ERR(f,d) fprintf(stderr,f,d)
#define FOR(i,a,n) for(int i=(a);i<(n);++i)

#define MAX 800
short n,a[MAX];
void qsort(short,short);
int solve(void);
int bin_src(short,short,short,short);

void debug(void) {
FOR(i,0,n)
ERR("%d",a[i]);
}

int main(void) {

freopen( "nrtri.in" , "r" , stdin );
freopen( "nrtri.out" , "w" , stdout );
scanf("%d",&n);
FOR(i,0,n)
scanf("%d", a + i );

qsort(0, n - 1 ); //debug();
 if(n<3) printf("0");
  else
   printf("%d\n",solve());
return 0;
}

void qsort(short st,short dr) {
short i=st,j=dr;
int x=a[(st+dr)/2];
while(i<j)
  {
   while(a[i]<x) ++i;
   while(a[j]>x) --j;
   if(i<=j)
     {
     int y=a[i]; a[i]=a[j]; a[j]=y;
     ++i; --j;
     }

  }
if(i<dr) qsort(i,dr);
if(j>st) qsort(st,j);
}

int solve(void) {
int res=0;
for(int i=0;i<n-2;++i)
for(int j=i+1;j<n-1;++j)
{
res+=bin_src(i,j,j+1,n-1);
}
ERR("%d",res);
return res;
}

int bin_src(short i,short j,short st,short dr) {
short m=(st+dr)/2;
if(st>dr) return 0;

if(a[i]+a[j]>=a[m]) {
//printf("%d %d %d %d\n",a[i],a[j],a[m],m-st+1);
return (m-st+1)+bin_src(i,j,m+1,dr);
}
 else return bin_src(i,j,st,m-1);
   }