Cod sursa(job #275328)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 13:17:15
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#define infile "nrtri.in"
#define outfile "nrtri.out"
#define nmax 801
int l[nmax]; //lungimea betisoarelor
int n; //numarul de betisoare

int divide(int p, int q)
	{
	int x=l[p];
	while(p<q)
		{
		while(p<q&&l[q]>=x) q--; //cel din dreapta e mai mare
		l[p]=l[q];
		while(p<q&&l[p]<=x) p++; //cel din stanga e mia mic
		l[q]=l[p];
		}
	l[p]=x; //plasam corect
	return p; //returnam pozitia
	}

void qsort(int p, int q)
	{
	int m=divide(p,q);
	if(p<m-1) qsort(p,m-1); //osrtam partea stanga
	if(m+1<q) qsort(m+1,q); //sortam partea dreapta
	}

//cauta cea mai din dreapta pozitie cu valoarea <=x, sau -1 daca nu gaseste
int cbin(int x)
	{
	int p=1,q=n; //intervalul in care cautam
	int m,poz=-1;
	while(p<=q)
		{
		m=(p+q)/2; //pozitia din mijloc
		if(l[m]<=x) 
			{
			poz=m; //salvam pozitia
			p=m+1; //cautam doar in partea dreapta
			}
		else q=m-1;
		}
	return poz; //returnam pozitia
	}

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

int calculeaza()
	{
	int nr=0; //numarul de triunghiuri ce se pot forma
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=i+1;j<n;j++)
			{
			k=cbin(l[i]+l[j]); //cautam pozitia ultimei lungimi ce poate forma un triunghi cu cele doua laturi
			if(k>0) nr+=k-j;
			}
	return nr;
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
qsort(1,n); //sortam betisoarele dupa lungime
printf("%d",calculeaza()); //afisem numarul de triunghiuri ce se pot forma

fclose(stdin);
fclose(stdout);
return 0;
}