Pagini recente » Cod sursa (job #1640642) | Cod sursa (job #2205429) | Cod sursa (job #1827564) | Cod sursa (job #1790064) | Cod sursa (job #1520349)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n, v[805],nr;
int Divide(int p, int q)
{ int st=p,dr=q,x=v[p];
while(st<dr)
{
while(st<dr && v[dr]>=x)
dr--;
v[st]=v[dr];
while(st<dr && v[st]<=x)
st++;
v[dr]=v[st];}
v[st]=x;
return st;
}
void qsort(int p, int q)
{ int m=Divide(p,q);
if(p<m)
qsort(p,m-1);
if(m<q)
qsort(m+1,q);
}
int main()
{int i,j,stg,dr,mij;
in>>n;
for(i=1;i<=n;i++)
in>>v[i];
qsort(1,n);
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
{stg=j;
dr=n+1;
while(dr-1>stg)
{mij=(stg+dr)/2;
if(v[mij]<=v[i]+v[j])
stg=mij;
else
dr=mij;
}
if(stg<=n)
nr+=n-stg;
}
out<<nr;
in.close();
out.close();
return 0;
}