Pagini recente » Cod sursa (job #1378434) | Cod sursa (job #870743) | Statistici mironiuc miriam (mironiucmiriam) | Cod sursa (job #1760652) | Cod sursa (job #275328)
Cod sursa(job #275328)
#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;
}