Cod sursa(job #528134)

Utilizator TodeaDariustodea darius TodeaDarius Data 2 februarie 2011 09:21:03
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 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);
	for(i=0;i<n-2;i++)
	{
		for(j=i+1;j<n-1;j++)
		{
			a=0;
			x=v[i]-v[j];
			st=j;dr=n-1;
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if(v[mij]==x)
				{
					a=1;
					break;
				}
				else
				{
					if(v[mij]<x)
					{
						dr=mij-1;
					}
					else
					{
						st=mij+1;
					}
				}
			}
			if(a==1)
			{
				nr=nr+mij-j;
			}
			else
			{
				j1=j+1;
				while(v[j1]>x)
				{
					j1=j1+1;
				}
				nr=nr+j1-j-1;
			}
		}
	}
	printf("%d",nr);
	return 0;
}