Cod sursa(job #322642)

Utilizator marinMari n marin Data 9 iunie 2009 15:33:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#define DIM 811
#include <algorithm>

using namespace std;

int V[DIM];
int n,m,i,j,p,u,s,tot,aux;

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);
	
	sort(V+1,V+n+1);
	
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++){
			s = V[i]+V[j];
			
			p = 1; u = n;
			while (p<=u) {
				m = p + (u-p)/2;
				if (V[m]<=s)
					p = m + 1;
				else
					u = m - 1;
			}
			
			aux = p;
			
			s = V[j]-V[i];
		
			p = 1; u = n;
			while (p<=u) {
				m = p + (u-p)/2;
				if (V[m]>=s)
					u = m - 1;
				else
					p = m + 1;
			}
			
			tot+=(aux-u-1);
			if (V[i]>=V[u+1]) 
				tot--;
			if (V[j]>=V[u+1])
				tot--;
		}
			
	FILE *g = fopen("nrtri.out","w");
	fprintf(g,"%d",tot/3);
	fclose(g);
		
	return 0;
}