Если зафиксировать 2 стороны, то синус угла между ними нужно минимизировать, т.е третью сторону минимизировать или максимизировать. То есть нужно попробовать 2 варианта: минимальная сторона больше b — a и максимальная меньше a+b

Сначала отсортируем массив по возростанию. Далее перебираем три последовательных числа с помощью for. Если из трех можно составить треугольник выводим эти числа. P.S. Являются ли отрезки треугольником можно проверить с помощью if(a+b>c&&b+c>a&&a+c>b&&abs(a-b)<c&&abs(a-c)<b&&abs(b-c)<a)

Если я правильно понял условие, то вот решение за O(n²).

У нас не больше 2N различных точек — концов отрезков. Построим граф: точки — вершины, а ребра — отрезки. Будем хранить в остортированном виде в какую точку мы можем попасть из текущей.

Переберем отрезок. У нас уже есть 2 точки треугольника, нужно определить третью. Для этого объединим, в какую третью точку мы можем попасть и из первой, и из второй одновременно (слить два отсортированных списка). Получили списочек треугольков, которые мы можем получить исспользуя 2 текущие точки (точки от выбранного отрезка) и еще третью (из слитых списков). Итого O(n²), только не ясно, тут квадрат подойдет или надо быстрее.

UPD: То, что я написал, разве не работает за линию? Ведь количество ребер у нас O(n), тогда в сумме сливание списков будет линейное же?

вот та же задача, но уже с ограничением n <= 1e5: http://acmp.ru/index.asp?main=task&id_task=594

у меня зашло решение, которое ищет ответ только среди 150 самых длинных отрезков, но это вроде неправда

Допустим мы отсортируем все длины отрезков. Не будут тогда нужные нам треугольники вида i, j, j + 1, где i < j?

Допустим стороны нашего треугольника имеют индексы i, j, k и i < j < k. Допустим i и k зафиксированны, тогда очевидно, что j должно быть как можно больше (чтобы высота была как можно меньше у треугольника, за основание отрезок k возьмем). Получается, что при заданных i и k и условии i < j < k либо a[i], a[j = k - 1], a[k] треугольник с минимальной площадью при фиксированных i и k (если правило треугольника соблюдается), либо такого нет.

Если так то, можно просто перебирать j, брать две стороны a[j], a[j + 1] и искать такое минимальное i, что a[i] > a[j + 1] - a[j].

https://www.dropbox.com/s/ljywzxkwf11gx75/Sbornik_2010.pdf?dl=0

Надеюсь страница 100 поможет в решении.

Пусть вырожденный треугольник по условию подходит. То есть, если есть такие i, j, k : a[i] + a[j] = a[k], нужно их уметь искать. Это аналог задачи 3-SUM. Задача эта хорошо изучена, быстрее чем за Θ(n²) её решать не умеют.

А лучшее по константе решение за Θ(n²) -- как раз описанный в первом посте метод двух указателей.

Кстати, на современных серваках 10⁹ простых операций заходят за секунду. 10⁸ зайдёт даже за 0.5 даже на очень слабом сервере.

UPD: 3-SUM при ограниченных числах решается через быстрое умножение многочленов. Если числа целые от 1 до C, для решения исходной задачи нам достаточно насчитать для каждой суммы двух сторон a+b, f[a+b] = max(b-a). После этого задача решится за O(C).