Cod sursa(job #420476)

Utilizator nandoLicker Nandor nando Data 19 martie 2010 14:08:21
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <vector>

using namespace std;

FILE* fin=fopen("nrtri.in","r");
FILE* fout=fopen("nrtri.out","w");

#define MAX 100000

int n,cnt=0;
vector<int>vec;


int main(){
	int k;
	fscanf(fin,"%d",&n);
	for(int i=0;i<n;i++){
		fscanf(fin,"%d",&k);
		vec.push_back(k);
	}
	sort(vec.begin(),vec.end());
	int beg,end,mdl,val,last;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			val=vec[i]+vec[j];
			beg=0,end=n-1,last=(n-1)/2;
			while(beg<=end){
				mdl=beg+(end-beg)/2;
				if(vec[mdl]<=val){
					last=mdl,beg=mdl+1;
				}else{
					end=mdl-1;
				}
			}
			cnt+=(j<=last)?(((i<=last)?last-1:last)-1):last;
		}
	}
	fprintf(fout,"%d ",cnt/2);
	fclose(fin);
	fclose(fout);
	return 0;
}