Cod sursa(job #3148998)

Utilizator stefanchpStefan Chiper stefanchp Data 5 septembrie 2023 17:41:41
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n;
int a[805];

int cautbin1(int val, int st, int dr)
{
	int mij, poz = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (a[mij] <= val)
		{
			poz = mij;
			st = mij + 1;
		}
		else if (a[mij] > val)
			dr = mij - 1;
	}
	return poz;
}

int cautbin2(int val, int st, int dr)
{
	int mij, poz = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (a[mij] >= val)
		{
			poz = mij;
			dr = mij - 1;
		}
		else if (a[mij] < val)
			st = mij + 1;
	}
	return poz;
}

int main()
{
	long long sol = 0;
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			int aux1 = cautbin1(a[i] + a[j], (j + 1), n);
			int aux2 = cautbin2(abs(a[j] - a[i]), (j + 1), n);
			if (aux1 != -1 && aux2 != -1)
				sol += (aux1 - aux2 + 1);
		}
	fout << sol;
	return 0;
}