Pagini recente » Cod sursa (job #2287644) | Cod sursa (job #2140436) | Cod sursa (job #3199263) | Cod sursa (job #2567945) | Cod sursa (job #2075524)
#include <stdio.h>
#include <algorithm>
const int MAX_N = 800;
int v[MAX_N + 1];
bool check_triangle(int i, int j, int k)
{
bool a, b, c;
a = v[i] <= v[k] + v[j];
b = v[j] <= v[i] + v[k];
c = v[k] <= v[j] + v[i];
return a && b && c;
}
bool compare(const int& lhs, const int& rhs)
{
return lhs > rhs;
}
int binsearch(int n, int i, int j)
{
int step = 1 << 10;
int r = 0;
while(step != 0)
{
if(r + step <= n && check_triangle(i, j, r + step))
r += step;
step /= 2;
}
return r;
}
int main()
{
FILE *fin = fopen("nrtri.in", "r"),
*fout = fopen("nrtri.out", "w");
int n;
int n_triangles;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; i++)
fscanf(fin, "%d", &v[i]);
std::sort(v + 1, v + n + 1, compare);
n_triangles = 0;
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
int k = binsearch(n, i, j);
int x = static_cast<int>(i <= k) + static_cast<int>(j <= k);
if(j < k)
n_triangles += k - j;
}
}
fprintf(fout, "%d", n_triangles);
fclose(fin);
fclose(fout);
return 0;
}