Задача предусматривает несколько возможных решений. При данных ограничениях (n ≤ 100) мы можем позволить перебор всевозможных троек фрагментов забора и выбрать максимальную площадь среди таковых. Такой алгоритм имеет кубическую сложность O(n3). Количество возможных треугольников, которые могут получится из n фрагментов равно , что для n=100 составляет всего 161700. Это подтверждает возможность простого перебора. Проще всего перебор осуществить в тройном вложенном цикле по некоторым переменным i, j и k – номерам фрагментов. Во избегании возможных повторов следует организовать цикл таким образом, чтобы выполнялось условие: i
Алгоритмическая реализация вышеописанного:
read(n)
for i=1..n
read(x[i])
sm=-1
for i=1..n-2
for j=i+1..n-1
for k=j+1 to n
if(TriangleExitst(x[i], x[j], x[k])){
s = Geron(x[i], x[j], x[k])
if(s > sm){
sm=s; im=i; jm=j; km=k;
}
}
if(sm < 0) write(-1)
else write(sm, ' ', im, ' ', jm, ' ', km)
Эту задачу возможно решить более эффективно, используя меньше вычислений. Рассмотрим линейный алгоритм, сложность которого O(n). Мы можем отсортировать фрагменты забора по невозрастанию, сохраняя в отдельном массиве их первоначальные номера. Можно показать, что искомый треугольник будет состоять из фрагментов, стоящих рядом в отсортированном массиве. Пробегая по массиву слева направо мы можем линейно перебрать всевозможные тройки фрагментов и выбрать тройку с максимальной площадью. Общая сложность алгоритма будет соответствовать сложности алгоритма сортировки, который так же может быть линейным в силу дискретности возможных длин фрагментов (можно использовать сортировку подсчетом). Если бы длины фрагментов были вещественными, то сложность алгоритма возросла бы до O(n*ln(n)) в лучшем случае.
