题目描述
Call a set of positive integers triangular if it has size at least three and, for all triples of distinct integers from the set, a triangle with those three integers as side lengths can be constructed.
Given a set of positive integers, compute the number of its triangular subsets.
输入
The first line of input contains a single integer n (1 ≤ n ≤ 50), which is the number of integers in the set.
Each of the the next n lines contains a single integer x (1 ≤ x ≤ 109 ). These are the elements of the set. They are guaranteed to be distinct.
输出
Output a single integer, which is the number of triangular subsets of the given set.
样例输入 Copy
【样例1】
5
3
1
5
9
10
【样例2】
10
27
26
17
10
2
14
1
12
23
39
样例输出 Copy
【样例1】
2
【样例2】
58
题意：求出集合的个数，这些集合要满足，在该集合中任意选三个点可以构成三角形
将所有的边长进行按照从小到大进行排序之后，枚举两条边的起点和终点，然后计算出这两条边的和，求出在排序后的数组中在(a[j],sum)之间的能够组成的子集的数量进行计算，对于n个点，有2n - 1种选择方式
int n, m, k;
ll a[maxn];
int main() {
n = read;
ll ans = 0;
for (int i = 1; i <= n; i++) a[i] = read;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
for (int j = 1 + i; j <= n; j++) {
ll sum = a[i] + a[j];
int p = n;
while (a[p] >= sum) p--;
ans += (1LL << (p - j));
ans --;
}
}
cout << ans << endl;
return 0;
}