Cod sursa(job #700402)

Utilizator nrpcCiprian Stirbu nrpc Data 1 martie 2012 10:00:06
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int v[3001];
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);
	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;
			while(ok&&x<=y)
			{
				m=(x+y)/2;
				if(v[m-1]<b&&b<v[m])ok=0;
				else if(b==v[m])ok=0;
					else if(v[m]>b)y=m-1;
						else if(v[m]<b)x=m+1;
			}
			if(ok){m=j+1;ok=0;}
			ok1=1;
			x=j+1;y=n;
			while(ok1==1&&x<=y)
			{
				m1=(x+y)/2;
				if(v[m1+1]>a&&a>v[m1])ok1=0;
				else if(a==v[m1])ok1=0;
					else if(v[m1]>a)y=m1-1;
						else if(v[m1]<a)x=m1+1;
			}
			if(!ok&&!ok1)nr+=m1-m+1;
		}
	printf("%d",nr);
	return 0;
}