Cod sursa(job #681319)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 16 februarie 2012 21:40:14
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
#include<stdlib.h>

#define MaxN 805

int v[MaxN], sum[MaxN][MaxN], N;

int cmp(const void *x, const void *y){
	int *a = (int*) x;
	int *b = (int*) y;
	return *a - *b;
}

int cauta(int li, int ls, int s){
	int m;
	while(li <= ls){
		m = li + (ls -li) / 2;
		if(v[m] <= s){
			if(v[m + 1] > s || m == N)
				return m;
			else
				li = m + 1;
		}
		else
			ls = m - 1;
	}
	return 0;
}

int main(){
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out","w", stdout);

	int i, j, nr, k, s;
	scanf("%d", &N);
	for(i = 1; i <= N; i++)
		scanf("%d",&v[i]);
	qsort(v+1, N, sizeof(int), cmp);
	for(i = 1; i <= N; i++)
		for(j = 1; j <= N; j++)
			if(i!=j)
				sum[i][j] = v[i] + v[j];
	nr = 0;
	s = 0;
	for(i = 1; i < N - 1; i++)
		for(j = i + 1; j < N; j++){
			/*for(k = j + 1; k <= N; k++){
				if(sum[i][j] >= v[k] && sum[j][k] >= v[i] && sum[k][i] >= v[j])
					nr++;*/
			s = v[i] + v[j];
			k = cauta(j+1, N, s);
			if(k)
				nr = nr + k - j;
			}
	printf("%d\n", nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}