Треугольники
У Глеба есть n
отрезков.
Глеб — большой любитель геометрии и всяких бесполезных действий. Поэтому он хочет выяснить, сколько различных невырожденных треугольников у него получится составить из всех имеющихся у него отрезков.
Два треугольника считаются различными, если хотя бы одна из сторон треугольников различна.
Два отрезка считаются различными, если различаются их номера в порядке ввода.
Входные данные
В первой строке записано число n
, 3⩽n⩽4000.
В следующих строках записаны длины отрезков 1⩽ai⩽109
.
Выходные данные
Вывести одно число — количество треугольников.
ВВОД:
3
1
1
10
ВЫВОД:
0
ВВОД2:
3
3
4
5
ВЫВОД2:
1
Напишите код на с++
Ответы
Ответ:
Для решения данной задачи, можно использовать язык C++. Вам понадобится прочитать входные данные, обработать их и вычислить количество треугольников. Вот пример кода:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> segments(n);
for (int i = 0; i < n; ++i) {
cin >> segments[i];
}
// Сортируем отрезки по возрастанию
sort(segments.begin(), segments.end());
int count = 0;
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
// Проверяем, можно ли составить треугольник
if (segments[i] + segments[j] > segments[k]) {
count++;
} else {
// Так как отрезки отсортированы, дальше не будем проверять
break;
}
}
}
}
cout << count << endl;
return 0;
}
```
Пожалуйста, примените этот код в своей среде разработки C++ для решения задачи о количестве треугольников. Запустите программу, введите входные данные, и она должна вывести количество треугольников в соответствии с заданными отрезками.