Cod sursa(job #803364)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 27 octombrie 2012 14:30:13
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>

#define Nmax 801

#define swap(a,b) a^=b^=a^=b

int V[Nmax], N, sol;

int get_piv(int st, int dr) {
	int i = st-1, j = dr+1, val = V[(st+dr)/2];
	
	while(1) {
		do { i++; } while(V[i] < val);
		do { j--; } while(V[j] > val);
		if(i<j)
			swap(V[i],V[j]);
		else
			return j;
	}
}

void quick_sort(int st, int dr) {
	if(st<dr) {
		int pivot;
		pivot = get_piv(st,dr);
		quick_sort(st, pivot-1);
		quick_sort(pivot+1, dr);
	}
}

int binary_search(int val) {
	int putere, i;
	
	for(putere=1; putere<=N; putere<<=1);
	for(i=1; putere; putere>>=1)
		if(i+putere<=N && V[i+putere]<=val)
			i+=putere;
	return i;
}
	
int main() {
	
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	
	int i, j, k, poz;
	
	scanf("%d",&N);
	for(i=1; i<=N; i++)
		scanf("%d",&V[i]);
	
	quick_sort(1,N);
	
	for(i=1; i<=N-1; i++)
		for(j=i+1; j<=N; j++) {
			poz = binary_search(V[i]+V[j]);
			sol+=(poz-j);
		}
		
	printf("%d\n",sol);
	
	return 0;
}