Cod sursa(job #414959)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 10 martie 2010 19:11:49
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define DIM 801

int v[DIM];

int n;
int u,p,mij;
int i,j,aux;
int a,b,c;
int dif,sum,poz1,poz2;

int main(){
	
	FILE*f1=fopen("nrtri.in","r");
	fscanf(f1,"%d",&n);
	for(i=1; i<=n; i++)
		fscanf(f1,"%d",&v[i]);
	fclose(f1);
	
	for(i=1; i<n; i++)
		for(j=i+1; j<=n; j++)
			if(v[i]>v[j]){
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;				
			}
	
	for(i=1; i<n; i++)
		for(j=i+1; j<=n; j++){			
			a = v[i];
			b = v[j];
			
			sum = a + b;
			dif = (a>b?a:b) - (a<b?a:b); 
			
			p = 1;
			u = n;
			while(p <= u){
				mij = p + (u - p)/2;
				if(v[mij] < dif)
					p = mij + 1;
				else
					u = mij - 1;
			}
			poz1 = p;
			
			p = 1;
			u = n;
			while(p <= u){
				mij = p + (u - p)/2;
				if(v[mij] <= sum)
					p = mij + 1;
				else
					u = mij - 1;
			}
			poz2 = u;	
			
			c += poz2 - poz1 + 1;
			if(poz1<=i && i<=poz2)
				c--;
			if(poz1<=j && j<=poz2)
				c--;			
		}
	
	
	FILE*f2=fopen("nrtri.out","w");
	fprintf(f2,"%d",c/3);
	fclose(f2);	
	
	return 0;
}