Cod sursa(job #57302)

Utilizator swift90Ionut Bogdanescu swift90 Data 1 mai 2007 18:23:01
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int lat[801];
int main(){
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int n,i,j,s,p,u,mij;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&lat[i]);
	sort(lat,lat+n);
	
	s=0;
	for(i=0;i<n-2;i++){
		for(j=i+1;j<n-1;j++){
			p=j+1;
			u=n-1;
			while(p<u){
				mij=(p+u)/2;
				if(lat[i]+lat[j]<=lat[mij])
					u=mij;
				else
					p=mij+1;
			}
			while((lat[i]+lat[j]<lat[p])&&(p>j))
				p--;
			if((p>j)&&(lat[i]+lat[j]>=lat[p]))
				s=s+p-j;
		}
	}
	
	printf("%d\n",s);
	
	return 0;
}