Cod sursa(job #629052)

Utilizator ContraPunctContrapunct ContraPunct Data 2 noiembrie 2011 16:45:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<cstdio>
#include<fstream>
#include<vector>
#include <algorithm>
#define Nmax 801
using namespace std;
vector<int> bat; 
int n;
void ReadData()
{
	int i,x;
	ifstream fin("nrtri.in");
	fin>>n;
	for(i=0;i<n;i++)
	{
		fin>>x;
		bat.push_back(x);
	}
	sort(bat.begin(),bat.end());
	for(i=0;i<n;i++)
	{
		//printf("%d ",bat[i]);
	}
}
void Sol()
{
	ofstream fout("nrtri.out");
	int a,b,nr=0,stg,drp,m,suma;
	for(a=0;a<n;a++)
		for(b=a+1;b<n;b++)
		{
			suma = bat[a]+bat[b];
			stg = b+1;
			drp = n-1;
			int ok = -1;
			while(stg<=drp)
			{
				m = stg + (drp-stg)/2;
				if( suma >= bat[m] ) 
				{
					ok = stg; 
					stg = m+1;
				}
				else
				{
					drp = m-1;
				}	
			}
			if( ok == -1 )
				;
			else
				nr+= (ok-b);
		}
	fout<<nr<<"\n";
}
			
int main()
{	
	ReadData();
	Sol();
	return 0;
}