Cod sursa(job #2256250)

Utilizator memecoinMeme Coin memecoin Data 8 octombrie 2018 12:33:46
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
 
using namespace std;

int n;

vector<int> a;

int find(int l, int h, int x) {
	if (l > h) {
		return -1;
	}

	int mid = (l + h) / 2;

	if (mid == h) {
		if (a[mid] >= x) {
			return mid;
		}
		else {
			return -1;
		}
	}

	if (a[mid] >= x && a[mid + 1] < x) {
		return mid;
	}
	
	if (a[mid] > x) {
		return find(mid + 1, h, x);
	}

	return find(l, mid - 1, x);

}

int main() {
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		a.push_back(x);
	}

	sort(a.begin(), a.end(), greater<int>());

	int sol = 0;

	for (int i = 0; i < n; ++i) {
		int x = a[i];
		for (int j = i + 1; j < n; ++j) {
			int y = a[j];

			int ndx = find(j + 1, n - 1, x - y);

			if (ndx != -1) {
				sol += ndx - j;
			}
		}
	}

	printf("%d", sol);

	return 0;
}