Cod sursa(job #314602)

Utilizator drag0s93Mandu Dragos drag0s93 Data 12 mai 2009 10:48:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define IN "nrtri.in","r",stdin
#define OUT "nrtri.out","w",stdout
int N;
int V[900];
int main()
{
	freopen(IN);
	freopen(OUT);
	scanf("%d",&N);
	int st = 1 , dr = N  , m;
	for(int i = 1; i <= N ; ++i)	scanf("%d",&V[i]);
	sort(V + 1 , V + 1 + N);
	int per = 0;
	for(int i = 1 ; i <= N ; ++i)
		for(int j = i + 1 ; j <= N ; ++j)
		{
			st = j + 1;
			dr = N;
			int sol = j;
			while(st <= dr)
			{
				m = (st + dr) / 2;
				if(V[i] + V[j] >= V[m])
				{
					st = m + 1;
					sol = m;
				}
				else if(V[i] + V[j] < V[m])
					dr = m - 1;
			}
			per += sol - j;
		}
	printf("%d\n",per);
	return 0;
}