Cod sursa(job #1291112)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 12 decembrie 2014 11:57:15
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, p, u, sum, nr, mid;
int v[801];
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int main(){
	fin>> n;
	for(i = 1; i <= n; i++){
		fin>> v[i];
	}
	sort(v + 1, v + n + 1);
	for(i = 1; i < n - 1; i++){
		for(j = i + 1; j < n; j++){
			sum = v[i] + v[j];
			p = j + 1;
			u = n;
			while(p <= u){
				mid = (p + u) / 2;
				if(v[mid] <= sum){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			nr += u - j;
		}
		
	}
	fout<< nr;
	return 0;
}