Cod sursa(job #2326712)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 23 ianuarie 2019 21:41:32
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <algorithm>

#define input "nrtri.in"
#define output "nrtri.out"
#define NMAX 805

using namespace std;

ifstream in(input);
ofstream out(output);

int N, dist[NMAX];

void Read_Data()
{
	in >> N;
	for (int i = 1; i <= N; i++)
		in >> dist[i];
	sort(dist + 1, dist + 1 + N);
}

void Solve()
{
	int counter = 0;
	for (int i = 1; i <= N - 2; i++)
	for (int j = i + 1; j <= N - 1; j++)
	{
		// Cautam printre valori cea mai mare valoare strict mai mica sau egala cu suma primelor 2
		int st = j + 1, dr = N;
		int p = -1;
		while (st <= dr)
		{
			int middle = (st + dr) / 2;
			if (dist[i] + dist[j] >= dist[middle])
				p = middle, st = middle + 1;
			else dr = middle - 1;
		}
		if (p != -1) counter = counter + p - j;

	}
	out << counter;
}

int main()
{
	Read_Data();
	Solve();
	return 0;
}