Cod sursa(job #2257589)

Utilizator yo_andrei_2003Murica Andrei yo_andrei_2003 Data 10 octombrie 2018 11:03:46
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[801];
int main()
{
	int n, i, l, mij, st, dr, sum=0, el;
	FILE *fin, *fout;
	fin=fopen("nrtri.in" ,"r");
	fout=fopen("nrtri.out" ,"w");
	fscanf(fin, "%d" ,&n);
	for(i=1;i<=n;i++) {
		fscanf(fin, "%d" ,&v[i]);
	}
	sort (v+1, v+n+1);
	for (i=1;i<=n-2;i++) {
		for (l=i+1;l<=n-1;l++) {
			st=l+1;
			dr=n;
			el=-1;
			while (st<=dr) {
					mij=(st+dr)/2;
				if (v[mij]>v[i]+v[l]) {
					dr=mij-1;
				}
				else {
					el=1;
					st=mij+1;
				}
			}
			if (el==1) {
			sum+=(mij-l);
			}
			//fprintf(fout, "%d %d\n" ,mij ,l);
		}
	}
	fprintf(fout, "%d" ,sum);
    return 0;
}