Pagini recente » Cod sursa (job #830947) | Cod sursa (job #2184555) | Cod sursa (job #1601162) | Cod sursa (job #404497) | Cod sursa (job #362751)
Cod sursa(job #362751)
#include<fstream>
#define dmax 803
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n,x[dmax],sol;
int sf(const void *a,const void *b)
{ return ( *(int*)a - *(int*)b );
}
int bs(int l,int r,int i,int j)
{ int m;
if(r==0)
{ if(x[0]+x[j]>=x[i]) return 0;
else return j;
}
while(l<r)
{ m=(l+r)/2;
if(r-l==1)
{ if(x[l]+x[j]>=x[i])
return l;
else if(x[r]+x[j]>=x[i])
return r;
else return j;
}
if(x[m]+x[j]==x[i])
{ while(x[m-1]+x[j]==x[i])
m--;
return m;
}
else if(x[m]+x[j]>x[i])
r=m;
else if(x[m]+x[j]<x[i])
l=m;
}
}
int main()
{ int i,j,q;
in>>n;
for(i=0;i<n;i++)
in>>x[i];
in.close();
qsort( (void*)x,n,sizeof(x[0]),sf);
for(i=n-1;i>1;i--)
for(j=i-1;j>0;j--)
{ q=bs(0,j-1,i,j);
sol=sol+j-q;
}
out<<sol;
out.close();
return 0;
}