Pagini recente » Cod sursa (job #1558029) | Cod sursa (job #1913045) | Cod sursa (job #1010388) | Cod sursa (job #2073963) | Cod sursa (job #2002359)
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[802];
void quicksort(int start, int stop)
{
int i=start,j=stop,nr;
nr=v[(i+j)/2];
do
{
while (i<stop && nr>v[i]) ++i;
while (j>start && nr<v[j]) --j;
if (i<=j)
swap(v[i++],v[j--]);
}while(i<=j);
if (j>start) quicksort(start,j);
if (i<stop) quicksort(i,stop);
}
int binara(int x, int lo, int hi)
{
int mi;
while (lo<hi)
{
mi=lo+(hi-lo)/2;
if (v[mi]>=x)
hi=mi;
else
lo=mi+1;
}
mi=lo+(hi-lo)/2;
if (v[mi] < x)
mi--;
return mi;
}
int main()
{
fin >> n;
for (int i=1;i<=n;i++)
fin >> v[i];
quicksort(1,n);
int nrtri=0,l1=n-2,l2=n-1;;
for (int i=1;i<=l1;i++)
{
for (int j=i+1;j<=l2;j++)
{
nrtri+=(binara(v[i]+v[j],j+1,n-1)-j);
}
}
fout << nrtri;
return 0;
}