Mai intai trebuie sa te autentifici.
Cod sursa(job #96746)
Utilizator | Data | 3 noiembrie 2007 12:16:48 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.75 kb |
#include<stdio.h>
#include<stdlib.h>
int comp(const void *a, const void *b){
int *aa=(int *)a, *bb=(int *)b;
int x=*aa, y=*bb;
return x-y;
}
int main () {
int n,v[800],i,nr=0,j,p,u,m,ok;
FILE *in=fopen("nrtri.in","r"), *out=fopen("nrtri.out","w");
fscanf(in,"%d",&n);
for(i=0;i<n;i++)
fscanf(in,"%d",&v[i]);
qsort(v,n,sizeof(v[0]),comp);
for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++){
ok=0;
p=j+1;
u=n-1;
m=(p+u)/2;
while(p!=u){
m=(p+u)/2;
if(v[i]+v[j]>v[m])
p=m+1;
if(v[i]+v[j]<v[m])
u=m;
if(v[i]+v[j]==v[m]){
p=u;
ok=1;
}
}
if(ok)
nr+=m-j;
else
if(v[i]+v[j]>=v[p])
nr+=p-j;
}
fprintf(out,"%d\n",nr);
fclose(in);
fclose(out);
return 0;
}