Обозначим за L максимальную длину палочки.
Для начала заметим, что можно перебрать длины двух сторон прямоугольника и проверить можно ли из данных палочек получить четыре нужные. Сложность такого решения O(L2). Правильно реализованное подобное решение может набирать не менее 24 баллов.
Далее заметим, что при зафиксированной первой стороне выгодно, чтобы вторая была наибольшей возможной. Более того, если мы можем получить прямоугольник, взяв в качестве второй стороны k, то мы также сможем получить прямоугольник с взятой второй стороной с длиной менее k. Также, если из данных палочек невозможно получить четыре палочки для выбранных первой и второй стороны, то также невозможно выбрать большую вторую сторону. Отсюда видим, что для выбора второй стороны можно использовать двоичный поиск. Сложность данного решения и оно набирает не менее 52 баллов.
Попробуем проанализировать ответ. Существует пять случаев получения сторон прямоугольника из исходных палочек:
Так как L может быть довольно велико, для оценки площади выбранного прямоугольника нужно использовать умножение и сравнение длинных чисел. Данная модификация предыдущего решения набирает 100 баллов.