Pagini recente » Cod sursa (job #694355) | Cod sursa (job #2942495) | Cod sursa (job #1726342) | Cod sursa (job #143963) | Cod sursa (job #1526114)
#include<iostream>
#include<fstream>
#include<algorithm>
#define FIN "nrtri.in"
#define FOUT "nrtri.out"
#define MAXN 801
using namespace std;
ifstream f(FIN);
ofstream g(FOUT);
int v[MAXN];
int n;
bool isTriangle(int a, int b, int c)
{
if( a + b >= c && a + c >= b && b + c >= a)
return true;
else return false;
}
int searchRight(int a, int b, int left, int right)
{
int step = 1;
int i = left;
for(step = 1; step < n; step <<= 1);
for(i=left; step != 0; step >>= 1 )
{
if( (i+step) <= right && a + b >= v[i+step] )
i += step;
}
if(i == left)
return -1;
else return i;
}
int searchLeft(int a, int b, int left, int right)
{
int step = 1;
int i = right;
for(step = 1; step < n; step <<= 1);
for(i=right; step != 0; step >>= 1 )
{
if( (i-step) > left && a + b >= v[i-step] )
i -= step;
}
if(i == right && isTriangle(a, b, v[i]) == false)
return -1;
else return i;
}
int main()
{
f >> n;
int counter = 0;
for(int i=1; i<=n; i++)
f >> v[i];
sort(v + 1, v + n + 1);
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<= n; j++)
{
int right = searchRight(v[i], v[j], j, n);
int left = searchLeft(v[i], v[j], j, n);
if(right != -1 && left != -1)
{
counter += right - left + 1;
}
}
}
cout << counter ;
g << counter;
return 0;
}