Cod sursa(job #414948)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 10 martie 2010 18:59:58
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
FILE*f=fopen("nrtri.in","r");
FILE*g=fopen("nrtri.out","w");
int n,v[801],i,j,u,p,m,s,nr,dif,aux;
//int w[801];
int main () {
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	sort(v+1,v+n+1);
	for(i=1;i<n;i++){
		for(j=i+1;j<=n;j++){
			s=v[i]+v[j];
			dif=v[j]-v[i];
			//cautam valorile din sir situate intre s si dif
			//cautam cea mai mica pozitie pe care se afla un element >=dif
			p=1; u=n;
			while(p<=u){
				m=p-(p-u)/2;
				if(v[m]>=dif)
					u=m-1;
				else
					p=m+1;
			}
			//valoarea cautata ramane in p
			aux=p;
			if(aux==i||aux==j)
				aux++;
			//cautam cea mai mare pozitie pe care se afla un element <=s
			p=1; u=n;
			while(p<=u){
				m=p-(p-u)/2;
				if(v[m]<=s)
					p=m+1;
				else
					u=m-1;
			}
			if(u==j)
				u++;
			//valoarea cautata ramane in u
			nr+=(u-aux+1);
		}
	}
	nr=nr/3-3;
	fprintf(g,"%d",nr);
	
	fclose(f);
	fclose(g);
	return 0;
}