Cod sursa(job #275210)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 12:06:15
Problema Numarare triunghiuri Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#define infile "nrtri.in"
#define outfile "nrtri.out"
#define nmax 801
#define lmax 30*1001
int l[nmax]; //lungimea betisoarelor
int x[lmax]; //x[i]=numarul de betisoare cu lungimea mai mica sau egala cu i
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
	}

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

void preproceseaza()
	{
	int i,j=1;
	for(i=1;i<lmax;i++)
		{
		x[i]=x[i-1]; //avem cel putin acelasi numar cu i-1
		if(l[j]==i) //daca betisorul are lungimea care ne trebuie
			while(l[j]==i) { x[i]++; j++; } //numarul betisoarelor este acelasi
		}
	}

int calculeaza()
	{
	int nr=0; //numarul de triunghiuri ce se pot forma
	int i,j;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			nr+=x[l[i]+l[j]]-x[l[j-1]]-1; // lungimea minima este >= l[j], iar lungimea maxima este suma celor doua lungimi
	return nr;
	}

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

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

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