Cod sursa(job #2211777)

Utilizator primeBasso Nicolae prime Data 11 iunie 2018 20:23:57
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>						//Binary search task
#include <fstream>
#include <algorithm>
#include <set>

using namespace std;

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

int a[810], s;
int i, j, n, l, r, m, c;				//l - left; r - right; m - middle; c - count; s - sum of a[i] and a[j]
set < pair < int, int > > used;

//4
//2 3 4 7

int main(){
	in >> n;
	
	for(i = 1; i <= n; i++)
		in >> a[i];
		
	sort(a, a + n + 1);
		
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++){
			if(i != j){
				l = 1;
				r = n;
	
				m = l + (l + r) / 2;
				s = a[i] + a[j];												
				
				while(l <= r){
					if(a[m] >= s){
						r = m - 1;
						m = (l + r) / 2;
					}
					else if(a[m] < s){
						if(m != i && m != j && a[i] + a[j] >= a[m] && a[i] + a[m] >= a[j] && a[j] + a[m] >= a[i] && !used.count(make_pair(j, i))){
							used.insert(make_pair(i, j));
							//cout << a[i] << " " << a[j] << " " << a[m] << "\n";
							c++;
						}
						l = m + 1;
						m = (l + r) / 2;
					}
				}
			}
		}
		
	out << c << endl;
		
	return 0;
}