Cod sursa(job #773245)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 1 august 2012 11:21:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

vector < int > v;
vector < int > :: iterator t;
int n, res, x, i, j;

int bs(int st, int end, int val)
{
	int mid;
	while(st <= end)
	{
		mid = (st + end) / 2;
		if(v[mid] > val)
			end = mid - 1;
		else
			st = mid + 1;
	}
	
	return st - 1;
}
int main()
{
	FILE *f = fopen("nrtri.in", "r");
	
	fscanf(f, "%d", &n);
	
	for(i = 0; i < n; ++i)
		fscanf(f, "%d", &x), v.push_back(x);
	
	fclose(f);
	
	sort(v.begin(), v.end());
	
	int max_i = n - 2, max_j = n - 1;
	
	for(i = 0; i < max_i; ++i)
		for(j = i + 1; j < max_j; ++j)
		{
			x = v[i] + v[j];
			x = bs(j, n - 1, x);
			res += x - j;
		}
		
	FILE *g = fopen("nrtri.out", "w");
	
	fprintf(g, "%d\n", res);
	
	fclose(g);
	
	return 0;
}