Pagini recente » Cod sursa (job #1853537) | Cod sursa (job #2833442) | Cod sursa (job #823992) | Cod sursa (job #2812022) | Cod sursa (job #1793873)
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
int v[801][2], A[801][2], n, suma, diferenta, prim, last;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
void citire()
{
fin>>n;
for(int i = 1; i <= n; ++i)
{
fin>>v[i][1];
v[i][0] = i;
}
}
void sortare(int p, int u)
{
if(p < u)
{
int p1 = p;
int mid = (p + u) / 2 , mid1 = mid + 1, t, x = p1;
sortare(p,mid);
sortare(mid + 1,u);
while(p <= mid and mid1 <= u)
{
if(v[p][1] <= v[mid1][1])
{
A[x][1] = v[p][1];
A[x][0] = v[p][0];
++x;
++p;
}
else
{
A[x][1] = v[mid1][1];
A[x][0] = v[mid1][0];
++mid1;
++x;
}
}
while(p <= mid)
{
A[x][1] = v[p][1];
A[x][0] = v[p][0];
++x;
++p;
}
while(mid1 <= u)
{
A[x][1] = v[mid1][1];
A[x][0] = v[mid1][0];
++x;
++mid1;
}
for(int i = p1; i <= u; ++i)
{
v[i][1] = A[i][1];
v[i][0] = A[i][0];
}
}
}
void cautbin1(int p, int u)
{
if(p <= u)
{
int mid = (p + u) / 2;
if(v[mid][1] <= suma)
{
if(v[mid][1] >= diferenta)
{
if(mid < prim) prim = mid;
cautbin1(p, mid - 1);
}
else cautbin1(mid + 1, u);
}
else cautbin1(p, mid - 1);
}
}
void cautbin2(int p, int u)
{
if(p <= u)
{
int mid = (p + u) / 2;
if(v[mid][1] <= suma)
{
if(v[mid][1] >= diferenta)
{
if(mid > last) last = mid;
}
cautbin2(mid + 1, u);
}
else cautbin2(p, mid - 1);
}
}
int main()
{
int tot = 0;
citire();
sortare(1, n);
for(int i = 1; i <= n - 2; ++i)
for(int j = i + 1; j <= n - 1; ++j)
{
suma = v[i][1] + v[j][1];
diferenta = abs(v[i][1] - v[j][1]);
prim = 90100;
last = -1;
cautbin1(j + 1, n);
cautbin2(j + 1, n);
if(last != -1)
{
tot += (last - prim + 1);
}
}
fout<<tot;
}