Pagini recente » Cod sursa (job #1234883) | Cod sursa (job #2036757) | Cod sursa (job #1721388) | Cod sursa (job #871885) | Cod sursa (job #1965563)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream F("nrtri.in");
ofstream G("nrtri.out");
int n, mij, st, dr, step, k, v[802], mini,m;
int main()
{
F >> n;
for(int i = 1; i <= n; ++ i)
F >> v[i];
sort(v + 1, v + n + 1);
for(int i = 1; i < n - 1; ++ i)
for(int j = i + 1; j < n; ++ j)
{
for(step = 1; step < n; step <<= 1);
for(m = j + 1; step; step >>= 1)
if(m + step <= n && v[m + step] <= v[i] + v[j])
m += step;
if(v[m] > v[i] + v[j]) m --;
mini = m;
for(step = 1; step < n; step <<= 1);
for(m = j + 1; step; step >>= 1)
if(m + step <= n && v[m + step] < v[j] - v[i])
m += step;
if(v[m] < v[j] - v[i]) m++;
k += mini - m + 1;
/*st = j + 1;
dr = n;
while(st <= dr)
{
mij = (st + dr) >> 1;
if(v[mij] >= v[j] - v[i])
dr = mij - 1;
else
st = mij + 1;
}
if(v[mij] < v[j]-v[i]) mij ++;
mini = mij;
st = j + 1;
dr = n;
while(st <= dr)
{
mij = (st + dr) >> 1;
if(v[mij] <= v[i] + v[j])
st = mij + 1;
else
dr = mij - 1;
}
if(v[j] + v[i] < v[mij]) mij --;
k+= mij - mini + 1;
*/
}
G << k;
return 0;
}