Cod sursa(job #714829)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 16 martie 2012 11:20:08
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int poz1,poz2,nr,V[900],dif,nt;
FILE*f=fopen("nrtri.in","r");
FILE*g=fopen("nrtri.out","w");

int cautare(int n,int e){
	int st=1,dr=nt,mij;
	while(st<=dr){
		mij=(st+dr)/2;
		if(V[mij]==n){
			if(e==1)
				dr=mij-1;
			else
				st=mij+1;
		}
		if(V[mij]>n){
			if(e==1){
				if(V[mij-1]<n)
					break;
				else
					dr=mij-1;
			}
			else{
				dr=mij-1;
			}
		}
		else{
			if(e==1){
				st=mij+1;
			}
			else{
				if(V[mij+1]>n)
					break;
				else
					st=mij+1;
			}
		}
	}
	return mij;
}

int main(){
	int i,j,sum=0;
	fscanf(f,"%d",&nt);
	for(i=1;i<=nt;i++)
		fscanf(f,"%d",&V[i]);
	sort(V+1,V+nt+1);
	for(i=1;i<=nt;i++)
		for(j=i+1;j<=nt;j++){
			sum=V[i]+V[j];
			dif=abs(V[i]-V[j]);
			poz1=cautare(dif,1);
			poz2=cautare(sum,2);
			nr+=poz2-poz1+1;
			nr-=(j-poz1+1);
		}
	fprintf(g,"%d",nr);
	return 0;
}