Cod sursa(job #2616537)

Utilizator CibotaruMateiCibotaru Matei CibotaruMatei Data 18 mai 2020 20:03:50
Problema Numarare triunghiuri Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

short getBound(short target, short v[], short size, bool up) {
	if (target >= v[size - 1]) return size - 1;
	if (target <= v[0]) return 0;
	short max = size - 1, pivot = size/2, min = 0;

	while (pivot != min && pivot != max) {
		if (target == v[pivot]) return pivot;
		if (target > v[pivot]) min = pivot;
		else max = pivot;

		pivot = (max + min) / 2;
	}

	if (up) return max;
	else return min;
}

int main()
{
	fstream f("nrtri.in", ios::in);
	
	short n;
	f >> n;
	short* b = new short[n];
	for (int i = 0; i < n; i++) f >> b[i];

	f.close();

	f.open("nrtri.out", ios::out);

	sort(b, b + n);
	int total = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			short up = getBound(b[i] + b[j], b, n, false), down = getBound(abs(b[i] - b[j]), b, n, true);
			total += up - down + 1;
			if (i <= up && i >= down) total--;
			if (j <= up && j >= down) total--;
		}
	}
	
	f << total / 6;

	f.close();
}