Ещё одна задача на геометрию, чтобы освежить формулу площади треугольника перед вторым туром регионального этапа Всероссийской олимпиады школьников по информатике.
Давайте рассуждать. Кажется логичным, что следует взять три самых больших фрагмента и сделать из них забор. Что же может помешать? В каком случае получается ответ -1?
Ответ заключается в правиле треугольника, которое гласит, что в любом невырожденном треугольнике сумма двух сторон больше третьей стороны. То есть может случиться так, что из трёх самых больших фрагментов один будет настолько большой, что превысит сумму оставшихся двух. Тогда, очевидно, его надо выкинуть, он ни с какими другими фрагментами не сможет образовать треугольник, а вместо него стоит попробовать взять следующий по длине (из ТОП-4). И продолжать этот процесс пока не получится.
Но на самом деле и первое утверждение является неверным. Треугольник из трёх самых больших фрагментов может быть очень вытянутым (с большим тупым углом) и занимать меньшую площадь, чем более сбалансированный треугольник из меньших фрагментов.
Например, если имеются фрагменты с длинами 18, 10, 10 , 10. Тогда треугольник со сторонами 18, 10, 10 имеет площадь примерно 39.23. А треугольник со сторонами 10, 10, 10 - примерно 43.3.
Но верным остаётся тот факт, что если зафиксировать один фрагмент, то для максимизации площади два других фрагмента следует брать самые большие (не превышающие зафиксированный, чтобы не перебирать каждый треугольник по несколько раз).
Отсюда приходим к решению, что надо перебирать каждый фрагмент и находить для него первый и второй максимум, не превышающие его. И среди всех таких троек, удовлетворяющих правилу треугольника, найти максимальный по площади треугольник. Ограничения в задаче позволяют делать это "в лоб", но можно облегчить реализацию и использовать сортировку. Тогда все интересующие нас тройки фрагментов будут идти подряд.
Для вычисления площади треугольника будем использовать формулу Герона:
Обычно её использовать не рекомендую, потому что в ней есть долгая операция взятия квадратного корня и работа с дробными числами. Но когда у треугольника известны только длины его сторон (а не координаты вершин), другого варианта нет.
Библиотеку algorithm подключили для возможности использовать сортировку. И так как при сортировке порядок фрагментов поменяется, а нам вывести номера использованных, то для фрагмента придётся ещё запомнить его номер. Для этого используем pair и сделаем пару замен (len и num) для наглядности кода.
Теперь можно считать входные данные:
Так как нам надо перебирать фрагменты в порядке убывания, использовал реверсивные итераторы rbegin и rend, но можно было бы отсортировать обычным способом и развернуть массив или использовать лямбда-функцию в качестве компаратора.
Заведём переменные для ответа и пройдёмся по всему массиву:
Условие проверяет правило треугольника (в нашем случае достаточно проверять лишь одну сторону на соответствие, потому что они отсортированы), а внутри него записана формула Герона. Обычно при сравнении вещественных чисел надо быть очень осторожным, но в этой задаче можно с этим не заморачиваться, потому что входные числа целые и не очень большие, значит ближайшие площади треугольников будут отличаться довольно сильно. Но если делать всё честно, то лучше хранить квадрат площади (то есть не брать квадратный корень) в типе Rational, который описан здесь.
Осталось вывести ответ:
Если мы так и не нашли ни одного треугольника, то площадь останется равна 0 и следует вывести -1.
Да, задачу можно было бы решить простым перебором всех троек, но ведь всегда стоит стремиться к лучшему.
Предыдущий выпуск: Задача 147. Числа Фибоначчи
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.