Cod sursa(job #2257565)

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