Cod sursa(job #337775)

Utilizator pykhNeagoe Alexandru pykh Data 4 august 2009 22:55:09
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<stdlib.h>
#define N 805

int v[N], n,i ,j;

const char in[]="nrtri.in";
const char out[]="nrtri.out";

int compare( const void *a, const void *b)
	{
		return (*(int*)a - *(int*)b);
}

int BS()
	{
		int hi, lo, mid;
		for(lo=j+1, hi=n, mid=lo+(hi-lo)/2;lo<=hi;)
		{
			if(v[i]+v[j]>=v[mid] && v[i]+v[mid]>=v[j] && v[j]+v[mid]>=v[i])return 1;
		else if(v[mid]>v[i]+v[j])hi=mid-1, mid=lo+(hi-lo)/2;
			else lo=mid+1, mid=lo+(hi-lo)/2;}
		return 0;
}



int main()
	{int rez=0;
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%d", &n);
			for(i=1;i<=n;++i)
		scanf("%d", &v[i]);
		qsort(v+1, n, sizeof(int), compare);
		for(i=1;i<=n-2;++i)
			for(j=1;j<n;++j)
				if(BS())++rez;
		printf("%d\n",rez);
		return 0;
}