Pagini recente » Cod sursa (job #272098) | Cod sursa (job #662564) | Cod sursa (job #2809848) | Cod sursa (job #598963) | Cod sursa (job #914624)
Cod sursa(job #914624)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,nr;
void schimb(int i,int j)
{
int aux;
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
void sort(int l,int h)
{
int piv,i=l,j=h;
piv=(l+h)/2;
piv=v[piv];
while(i<=j)
{
while(v[i]<piv)
i++;
while(v[j]>piv)
j--;
if(i<=j)
schimb(i++,j--);
}
if(i<h)
sort(i,h);
if(j>l)
sort(l,j);
}
int caut(int x)
{
int i=0,pas=1<<9;
while(pas!=0)
{
if(i+pas<=n && v[i+pas]<x)
i+=pas;
pas/=2;
}
return i;
}
void solve()
{
int x,y,z,d;
for(x=n;x>2;x--)
{
for(y=x-1;y>1;y--)
{
z=v[x]-v[y];
if(z<=v[y])
nr+=(y-caut(z)-1);
else
break;
}
}
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>v[i];
sort(1,n);
solve();
out<<nr;
return 0;
}