Cod sursa(job #1594013)

Utilizator valentin50517Vozian Valentin valentin50517 Data 9 februarie 2016 09:22:49
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

bool comp(int a,int b) {return a < b;}
int N,A[1000],rs;
int cbin(int lim,int val){
	int step,i;
	for(step = 1;step < lim;step<<=1);
	for(i = 1;step;step>>=1)
		if(i+step < lim && A[i+step] <= val)
			i+=step;
	return i;
}

int main(){
	fin >> N;
	for(int i = 1;i<=N;i++){
		fin >> A[i];
	} 
	
	sort(A,A+N,comp);
	for(int i = N;i>0;i--)
		for(int j = i-1;j>1;j--){
			int dr = cbin(j,A[i] + A[j]);
			int st = cbin(j,max(A[i],A[j])-min(A[i],A[j]));
			//fout << st << ' ' << dr << ' ' << dr-st+1 - bool(A[st] < max(A[i],A[j])-min(A[i],A[j])) - bool(A[dr] > A[i] + A[j]) << '\n';
			if(dr == st && A[i] + A[j] > A[st] && A[i] + A[st] > A[j] && A[j] + A[st] > A[i])
				rs++;
			else
				rs+= dr-st+1 - bool(A[st] < max(A[i],A[j])-min(A[i],A[j])) - bool(A[dr] > A[i] + A[j]);
		}
	fout << rs;
			
			
	return 0;
}