Pagini recente » Cod sursa (job #876804) | Cod sursa (job #2140731) | Cod sursa (job #2572924) | Cod sursa (job #1348218) | Cod sursa (job #2075626)
#include <stdio.h>
#include <algorithm>
#include <assert.h>
//#define DEBUG
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 && (v[i] + v[j] >= v[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);
n_triangles = 0;
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
int k = binsearch(n, i, j);
if(j < k)
n_triangles += k - j;
}
}
#ifdef DEBUG
printf("testing...\n");
int n_tri_test = 0;
for(int i = 1; i < n - 1; i++)
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k <= n; k++)
n_tri_test += static_cast<int>(check_triangle(i, j, k));
printf("%d\n%d\n", n_triangles, n_tri_test);
assert(n_tri_test == n_triangles);
#endif
fprintf(fout, "%d", n_triangles);
fclose(fin);
fclose(fout);
return 0;
}