Cod sursa(job #629036)

Utilizator alexandrab0507Alexandra Beldica alexandrab0507 Data 2 noiembrie 2011 16:33:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
// cb1.cpp : Defines the entry point for the console application.
//


#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f;
ofstream g;
int n,i,a,b,j;
vector<int> l(805);


int fl(int key, int li, int lf) {
	if (li > lf) {
		return -1;
	}
	if (l[lf] < key) {
		return -1;
	}
	if (l[li] >= key) {
		return li;
	} 
	int m = (li + lf) / 2;
	if (l[m] < key) {
	return fl(key, m + 1, lf);
	} else {
		int candidate = fl(key, li, m - 1);
		return candidate == -1 ? m : candidate;
	}
}

int fr(int key, int li, int lf) {
	if (li > lf) {
		return -1;
	}
	if (l[li] > key) {
		return -1;
	}
	if (l[lf] <= key) {
		return lf;
	}
	int m = (li + lf) / 2;
	if (l[m] > key) {
		return fr(key, li, m - 1);
	} else {
	int candidate = fr(key, m + 1, lf);
		return candidate == -1 ? m : candidate;
	}
}

int main() {
	f.open("nrtri.in");
	g.open("nrtri.out");
	f>>n;
	int nr=0;
	for (i=0;i<n;i++)
		f>>l[i];
	sort(l.begin(),l.begin()+n);
	for (i=0;i<n-1;i++)
		for (j=i+1;j<n;j++) {
			a=fl(l[j]-l[i],j+1,n-1);
			b=fr(l[i]+l[j],j+1,n-1);
			if ((a!=-1)&&(b!=-1))
				nr+=b-a+1;
		}
	g<<nr;
	f.close();
	g.close();
	return 0;
}