Cod sursa(job #307196)

Utilizator Addy.Adrian Draghici Addy. Data 23 aprilie 2009 17:40:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

int v[801];
int n,i,j,w,poz;

int caut(int i, int j) {
  int p,u,m,suma;
  p = j+1;
  u = n;
  poz = 0;
  suma = v[i] + v[j];
	while (p <= u) {
	  m = p + (u-p)/2;
	  if (v[m] <= suma) {
		p = m+1;
		poz = m;
	  }
	  else
		u = m-1;
	}
  return poz;
}

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

  for (i=1; i<n; i++)
	for (j=i+1; j<=n; j++) {
	  caut(i,j);
	  if (poz)
        w += poz-j;
	}
	
  fprintf(g,"%d\n",w);
  
  fclose(f);
  fclose(g);
	
  return 0;
}