Cod sursa(job #770277)

Utilizator 5t3fristea stefan 5t3f Data 22 iulie 2012 16:46:55
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
// numarare triunghiuri.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "fstream"
#include "algorithm"
using namespace std;
int n;
int main()
{
	ifstream f("nrtri.in");
	ofstream g("nrtri.out");
	f>>n;
	int i;
	int a[800];
	for(i=0;i<n;i++)
		f>>a[i];
	sort(a,a+n);
	int j;
	int nr=0;
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++)
		{
			int p,u,m,x;
			x=a[i]+a[j];
			p=j+1;
			u=n-1;
			m=(p+u)/2;
			while(p!=u)
			{
				if(a[m]>x)
					u=m-1;
				if(a[m]<x)
					p=m+1;
				if(a[m]==x)
					break;
			}
			m=(p+u)/2;
			if(a[m]==x)
				nr+=(m-j);
			if((a[m]>=x)&&(a[m-1]<=x))
				nr+=(m-j)-1;
		}
	g<<nr;
	return 0;
}