Cod sursa(job #137075)

Utilizator free_coderDancu Ioana free_coder Data 16 februarie 2008 21:00:43
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#define DIM 802

long int n,i,sum,j,a,b;
long int v[DIM];

void cre(long int *v, long int n);
void corect(long int poz, long int *v, long int n);
void s(long int *v, long int n);


long int cautp(long int x,long int p, long int u) {
  long int m;
  while (p<=u) {
    m=(p+u)/2;
    if (x<=v[m])
      u=m-1;
    else
      p=m+1;
  }
  while (v[u]<x)
    u++;
  return u;
}


long int cautu(long int x,long int p, long int u) {
  long int m;
  while (p<=u) {
    m=(p+u)/2;
    if (x<v[m])
      u=m-1;
    else
      p=m+1;
  }
  while (v[p]>x)
    p--;
  return p;
}





int main(){
  FILE *f = fopen("nrtri.in","r");
  fscanf(f,"%d",&n);
  for (i=1;i<=n;i++)
    fscanf(f,"%d",&v[i]);
  fclose(f);

  s(v,n);
  v[n+1] = v[n]+1;

  sum=0;
  for (i=1;i<=n-2;i++)
    for (j=i+1;j<=n-1;j++)
      if (v[j]-v[i]>=v[j]) {
	a = cautp(v[j]-v[i],j+1,n);
	b = cautu(v[j]+v[i],j+1,n);
	if (b>=a)
	  sum = sum + (b-a+1);
      } else {
	a = cautp(v[j+1],j+1,n);
	b = cautu(v[j]+v[i],j+1,n);
	if (b>=a)
	  sum = sum + (b-a+1);
      }
  printf("%ld\n",sum);

  return 0;
}





void cre(long int *v, long int n){
  long int i,aux,c,p;
  for (i=2;i<=n;i++) {
    c = i;
    p = i>>1;
    while ((p)&&(v[c]>v[p])) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      c = p;
      p = p>>1;
    }
  }
}

void corect(long int poz, long int *v, long int n){
  long int aux,p,c;
  p = poz;
  c = p<<1;
  while (c<=n) {
    if ((c+1<=n) && (v[c+1]>v[c]))
      c++;
    if (v[c]>v[p]) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      p = c;
      c = p<<1;
    } else break;
  }

}

void s(long int *v, long int n) {
  long int i,aux,p,c;
  cre(v,n);
  for (i=n;i>1;i--) {
    aux = v[1];
    v[1] = v[i];
    v[i] = aux;
    corect(1,v,i-1);
  }
}