Cod sursa(job #2211786)

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

#define pb push_back

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 < vector < int > > used;
vector < int > sum;

//4
//2 3 4 7

int main(){
	in >> n;
	
	for(i = 1; i <= n; i++)
		in >> a[i];
		
	sort(a + 1, 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[m] >= a[j] && a[j] + a[m] >= a[i]){
							sum.pb(a[i]);
							sum.pb(a[j]);
							sum.pb(a[m]);
							
							sort(sum.begin(), sum.end());
							
							if(used.count(sum) == 0){
								used.insert(sum);
								//cout << a[i] << " " << a[j] << " " << a[m] << "\n\n";
								c++;
							}
							
							sum.clear();
						}
						l = m + 1;
						m = (l + r) / 2;
					}
				}
			}
		}
		
	out << c;
		
	return 0;
}