Cod sursa(job #156516)

Utilizator znakeuJurba Andrei znakeu Data 12 martie 2008 16:43:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 801

using namespace std;

int v[MAXN],n;

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	
	int nrtri=0,i,j,e,S,s,l,r;
	
	FILE *in=fopen("nrtri.in","r");
	
	fscanf(in,"%d",&n);
	for (i=0; i<n; i++)
		fscanf(in,"%d",&v[i]);
	fclose(in);
	
	sort(v,v+n);
	
	for (i=0; i<n-2; i++)
		for (j=i+1; j<n-1; j++)
		{
			s=j+1; e=n; S=v[i]+v[j];
			while (s!=e)
			{
				if (v[(s+e)/2]>S)
					e=(s+e)/2;
				else
					s=(s+e)/2+1;
			}
			if (v[s]<=S && v[s])
				s++;
			nrtri+=s-(j+1);
		}
	
	FILE *out=fopen("nrtri.out","w");
	fprintf(out,"%d\n",nrtri);
	fclose(out);
	
	return 0;
}