Cod sursa(job #700576)

Utilizator nrpcCiprian Stirbu nrpc Data 1 martie 2012 11:00:27
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int v[3002];
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int n,ok,m,m1,x,y,i,j,a,b,nr=0,ok1;
	scanf("%d",&n);
	v[n+1]=10000000;
	for(i=1;i<=n;i++)scanf("%d",&v[i]);
	sort(v+1,v+n+1);
	for(i=1;i<=n-2;i++)
		for(j=i+1;j<=n-1;j++)
		{
			a=v[i]+v[j];
			b=v[j]-v[i];
			x=j+1;y=n;
			ok=1;
			m=j+1;
			while(ok==1&&x<=y)
			{
				m1=(x+y)/2;
				if(v[m1]<=a&&a<v[m1+1])ok=0;
					else if(v[m1]>a)y=m1-1;
						else if(v[m1]<=a)x=m1+1;
			}
			if(!ok)nr+=m1-m+1;
		}
	printf("%d",nr);
	return 0;
}