Pagini recente » Cod sursa (job #463184) | Cod sursa (job #878121) | Cod sursa (job #955628) | Cod sursa (job #157954) | Cod sursa (job #1526511)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,i,j,s;
/*void qs(int st,int dr)
{
int i=st,j=dr;
int pivot=v[(st+dr)/2];
while(i<=j)
{
while(v[i]<pivot)i++;
while(v[j]>pivot)j--;
if(i<=j)
v[i]=v[i]+v[j]-(v[j]=v[i]),i++,j--;
}
if(st<j)
qs(st,j);
if(i<dr)
qs(i,dr);
}*/
int cautarebinara(int p,int q)
{
int st=p,dr=q,k=0,mij;
while(st<=dr && st<=q && dr>=p)
{
mij=(st+dr)/2;
if(v[mij]<=v[i]+v[j] && dr-st==0)
{return k;}
if(v[mij+1]<=v[i]+v[j])
k++,dr=mij-1;
else
st=mij+1;
}
return k;
}
int main()
{
in>>n;
for(i=1;i<=n;i++)
in>>v[i];
sort(v+1,v+n+1);
// qs(1,n);
for(i=1;i<=n;i++)cout<<v[i]<<" "; cout<<endl;
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
s+=cautarebinara(j+1,n);
out<<s;
return 0;
}