Pagini recente » Cod sursa (job #3175380) | Cod sursa (job #1772220) | Cod sursa (job #654568) | Cod sursa (job #1515979) | Cod sursa (job #63906)
Cod sursa(job #63906)
#include <stdio.h>
#include <stdlib.h>
int v[805],n;
int comp(const void *a, const void *b)
{
int *aa=(int*) a, *bb=(int*) b;
int x=*aa, y=*bb;
if (x<y)
return -1;
if (x>y)
return 1;
return 0;
}
int main()
{
int nrtri=0,i,j,kl=0,kr=0,l,r;
FILE *in=fopen("nrtri.in","r");
fscanf(in,"%d",&n);
for (i=0; i<n; i++)
fscanf(in,"%d",&v[i]);
fclose(in);
qsort(v,n,sizeof(v[0]),comp);
for (i=0; i<n-2; i++)
for (j=i+1; j<n-1; j++)
{
l=j+1; r=n-1; kl=(l+r)/2;
while (kl!=l && kl!=r)
{
if ((v[i]+v[j]>=v[kl])&&(v[j]+v[kl]>=v[i])&&(v[i]+v[kl]>=v[j]))
r=kl;
else
if (v[i]+v[j]>=v[kl])
l=kl;
else
r=kl;
kl=(l+r)/2;
}
if ((v[i]+v[j]>=v[kl-1])&&(v[j]+v[kl-1]>=v[i])&&(v[i]+v[kl-1]>=v[j]))
kl--;
l=j+1; r=n-1; kr=(l+r)/2;
while (kr!=l && kr!=r)
{
if ((v[i]+v[j]>=v[kr])&&(v[j]+v[kr]>=v[i])&&(v[i]+v[kr]>=v[j]))
l=kr;
else
if (v[i]+v[j]>=v[kl])
r=kr;
else
l=kr;
kr=(l+r)/2;
}
if ((v[i]+v[j]>=v[kr+1])&&(v[j]+v[kr+1]>=v[i])&&(v[i]+v[kr+1]>=v[j]))
kr++;
if (kr>=kl)
nrtri+=kr-kl+1;
}
FILE *out=fopen("nrtri.out","w");
fprintf(out,"%d\n",nrtri);
fclose(out);
return 0;
}