Cod sursa(job #526156)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 27 ianuarie 2011 16:10:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	freopen ("nrtri.in", "r", stdin);
	freopen ("nrtri.out", "w", stdout);
	
	int N;
	vector <int> B;
	
	scanf ("%d", &N);
	
	for (int i = 0; i < N; ++i)
	{
		int numar;
		scanf ("%d", &numar);
		
		B.push_back(numar);
	}	
	
	sort (B.begin(), B.end());
	
	//N^2logN
	
	int rezultat = 0;
	
	for (int i = 0; i < N; ++i)
		for (int j = i + 1; j < N; ++j)
		{
			int st = j + 1, dr = N - 1, lim = B[i] + B[j];
			
			while (st < dr - 1)
			{
				int mij = (st + dr)/2;
				
				if (B[mij] <= lim) st = mij;
				else dr = mij - 1;
			}	
			
			int ul;
			if (B[dr] <= lim) ul = dr;
			else if (B[st] <= lim) ul = st;
			else ul = st - 1;
			
			rezultat += (ul - j);
		}	
	
	printf ("%d", rezultat);	
		
	return 0;
}