Cod sursa(job #759519)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 18 iunie 2012 14:27:05
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define N 800

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int v[N];

int bin(int a, int b, int val) {
	int i;

	i = (a+b)/2;
	while(a <= b) {
		i = (a+b)/2;
		if(v[i] < val)
			a = i+1;
		else
			if(v[i] > val)
				b = i-1;
			else
				break;
	}

	return i;
}

int main() {
	int i,j,n,k = 0,x;

	f>>n;
	for(i = 0; i < n; i++)
		f>>v[i];
	
	sort(v,v+n);

	for(i = 0; i < n-2; i++) {
		for(j = i+1; j < n-1; j++) {
			x = bin(0,n-1,v[i]+v[j]);
			if(v[x] <= (v[i]+v[j]))
				k += (x - j > 0) ? (x-j) : 0;
			else
				k += (x-j-1 > 0) ? (x-j-1) : 0;
		}
	}

	g<<k;
	
	return 0;
}