Треугольник - 2

После окончания многолетней войны короли-победители решили разделить между собой захваченную территорию. Для того, чтобы избежать лишних споров, короли решили делить территорию следующим образом.

Каждому королю был предоставлен набор, состоящий из n отрезков L₁, . . . , L_n. Королям разрешается присоединять к их королевствам территорию, имеющую форму треугольника, составленного из имеющихся отрезков.

Помогите королю вашего королевства максимизировать площадь треугольника.

Входные данные

На первой строке входного файла INPUT.TXT задано число n (3 ≤ n ≤ 100000) - количество отрезков в наборе. В следующих n строках заданы длины отрезков в следующем формате.

Сначала указывается целое положительное число L - длина отрезка, а затем единица измерения (m, km, mile, uin, kairi, zhang, sen).

Напомним, что: 1mile = 1609m, 1km = 1000m, 1uin = 33m, 1kairi = 1852m, 1zhang = 3m и 1sen = 38m.

Длины всех отрезков не превосходят десяти километров. Гарантируется, что из заданных отрезков можно выбрать три отрезка так, что из них можно составить треугольник.

Выходные данные

В выходной файл OUTPUT.TXT выведите максимальную площадь (в таланг вахах) с точностью 10^-6 и номера трех отрезков в любом порядке (если ответов несколько, выведите любой). Помните, что один таланг вах равен четырем квадратным метрам.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]