Cod sursa(job #1721450)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 25 iunie 2016 18:05:25
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

int binary_search(std::vector<int>& v, int x, int start, int N) {
	
	int pos ; int step;
	
	for(step = 1; step < N ; step *= 2);
	
	for(pos = start - 1; step > 0; step /= 2)
		if(pos + step < N && v[pos + step] <= x)
			pos += step;
			
	return pos - start + 1;
}

int main() {
	
	int N, nrtri;
	FILE *fin = fopen("ntri.in", "r");
	FILE *fout = fopen("ntri.out", "w");
	
	fscanf(fin, "%d", &N);
	
	std::vector<int> v;
	for (int i = 0; i < N; i++) {
		int elem;
		fscanf(fin, "%d", &elem);
		v.push_back(elem);
	}
	
	std::sort(v.begin(), v.end());
	
	nrtri = 0;
	
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int x = v[i] + v[j];
				
			nrtri += binary_search(v, x, j + 1, N);
				
		}
	}
	
	fprintf(fout, "%d\n", nrtri);
	
	fclose(fin);
	fclose(fout);
	
}