Cod sursa(job #272624)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 martie 2009 15:46:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>

const int N = 801;

int n,v[N],nrt=0;

void citire()
{
	scanf ("%d",&n);
	for (int i = 1; i <= n; ++i)
		scanf ("%d",&v[i]);
}

int comparare (const void *p, const void *q)
{
	int x = *(int*)p, y = *(int*)q;
	if (x < y)
		return -1;
	if (x > y)
		return 1;
	return 0;
}

void sortare()
{
	qsort(v+1,n,sizeof(v[0]),comparare);
}

int cautare_binara(int nr,int l1)
{
	++nr;
	int l2 = n;
	/*
	while ((v[l1] != nr)&&(v[l2] != nr)&&(l1 + 1 < l2))
		if (v[(l1+l2)/2] > nr)
			l2 = (l1+l2)/2;
		else l1 = (l1+l2)/2;
	*/
	int m;
	while(l1!=l2)
	{
		m=(l1+l2)/2;
		if(nr<=v[m])
			l2=m;
		else
			l1=1+m;
	}
	--nr;
	if(v[l1]>nr)
		--l1;
	return l1;
}

void cautare()
{
	//int poz;
	for (int i = 1; i <= n-2; ++i)
		for (int j = i+1; j <= n-1; ++j)
		{
			nrt += cautare_binara(v[i]+v[j],j) - j;
			//for (int k = j+1; k <= poz; ++k)
				//printf ("%d %d %d\n",i,j,k);
		}
}

void afisare()
{
	printf ("%d",nrt);
}

int main()
{
	freopen ("nrtri.in","r",stdin);
	freopen ("nrtri.out","w",stdout);
	citire();
	sortare();
	cautare();
	afisare();
}