Cod sursa(job #629974)

Utilizator George25Raduta George Cristian George25 Data 4 noiembrie 2011 12:49:52
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int i,n,poz,sum,j,k,nr,a[801];

inline void cb(int x,int xx){
	int st,dr,mij;
	st=xx;
	dr=n;
	mij=(st+dr)/2;
	while (st<=dr){
		if (a[mij]<x)
		{
			poz=mij;
			st=mij+1;
			mij=(st+dr)/2;
		}
		else
		if (a[mij]>x)
		{
			dr=mij-1;
			mij=(st+dr)/2;
		}
		else
		if (a[mij]==x)
		{
			poz=mij;
			break;
		}
	}
}

int main(){
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; ++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for (i=1; i<=n-2; ++i)
	{
		for (j=i+1; j<=n-1; ++j)
		{
			sum=a[i]+a[j];
			cb(sum,j+1);
			for (k=poz; k>=j+1; --k)
				if (a[i]+a[j]>=a[k] && a[i]+a[k]>=a[j] && a[k]+a[j]>=a[i]) 
				{
					nr=nr+k-j;
					break;
				}
		}	
	}	
	printf("%d",nr);
	return(0);
}