Как можно более вертикально

На плоскости отмечено n точек. В каждой написано целое число: вес этой точки.
Гоша провёл на плоскости ломаную линию. Эта линия:
• начинается выше всех отмеченных точек,
• проходит через ноль или более точек,
• заканчивается ниже всех отмеченных точек.
Количество очков, которые получил Гоша — это сумма весов точек, через которые проходит ломаная, умноженная на величину cos α, где α — максимальный возможный угол
между направлением строго вниз и направлением движения по ломаной. Например,
если вся ломаная строго вертикальна, то α = 0. И наоборот, если какой-то отрезок
ломаной идёт снизу вверх, то α > 90o и cos α < 0.
Какое максимальное количество очков мог получить Гоша? Заметьте, что это число
не обязательно целое.
Формат входных данных
В первой строке записано целое число n — количество точек (1<= n <= 50). Каждая из
следующих n строк содержит описание одной точки и состоит из трёх целых чисел
xi, yi, wi — координат точки и её веса (1<= xi, yi, wi <=100). Все заданные на плоскости
точки различны.
Формат выходных данных
Выведите одно вещественное число: максимальное количество очков, которые мог
набрать Гоша. Ответ будет считаться верным, если он отличается от ответа жюри не
более чем на 0.01.

0

Пример входных и выходных данных

Миниатюры

 

0