Cod sursa(job #528170)

Utilizator marinutzacatana marina marinutza Data 2 februarie 2011 12:13:05
Problema Numarare triunghiuri Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int x[800],a,i,j,n,st,dr,gasit,mij,g,k,poz;
bool cmp(int a,int b)
{
	return a>=b;
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&x[i]);
	}
	sort(x,x+n,cmp);
	for(i=0;i<n-2;i++)
	{
		for(j=i+1;j<n-1;j++)
		{
			a=x[i]-x[j];
			st=j+1;dr=n-1;
			poz=-1;
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if(x[mij]==a)
				{
					poz=mij;
					st=mij+1;
				}
				else
				{
					if(x[mij]>a)
					{
						st=mij+1;
					}
					else
					{
						dr=mij-1;
					}
				}
			}
			if(poz>=0)
			{
				g=g+poz-j;
			}
			else
			{
				for(k=j+1;k<n;k++)
					if(x[i]<x[j]+x[k])
						g++;
					else
						break;
			}
		}
	}
				
				printf("%d",g);
				return 0;
}