Cod sursa(job #528662)

Utilizator TodeaDariustodea darius TodeaDarius Data 3 februarie 2011 08:39:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
	return (b<a);
}
int n,i,j,v[810],a,nr,j1,mij,st,dr,x;
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&v[i]);
	}
	sort(v,v+n,cmp);
	st=2;dr=n-1;
	for(i=0;i<n-2;i++)
	{
		for(j=i+1;j<n-1;j++)
		{
			a=-1;
			x=v[i]-v[j];
			st=j+1;dr=n-1;
			while(st<=dr)
			{
				mij=(st+dr)/2;
				
				if(v[mij]<x)
				{
					dr=mij-1;
				}
				else
				{
					st=mij+1;
				}
				
			}
			nr=nr+dr-j;
			
		}
	}
	printf("%d",nr);
	return 0;

}