21660번 - Распил бревен 스페셜 저지다국어

Лесопильный комбинат выполняет заказ на распил брусьев для строительства детского городка. Все готовые брусья должны иметь форму треугольных призм, основаниями которых являются равнобедренные треугольники. Для изготовления брусьев закуплены заготовки в виде половинок продольно распиленных бревен. Заготовки не являются идеальными половинками цилиндров, поэтому при изготовлении бруса необходимо учитывать форму заготовок. Комбинат заинтересован в изготовлении бруса с наибольшей возможной площадью поперечного сечения.

Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин (x₀, y₀), (x₁, y₁), …, (x_N, y_N) в порядке их следования. Координаты вершин ломанной удовлетворяют следующим условиям:

• x₀ < x₁ < x₂ < … < x_N;
• x_i = 0 для некоторого 0 < i < N;
• y₀ =  y_N = 0 
• для всех i от 1 до (N – 1) выполнено условие y_i > 0.

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

• основание треугольника лежит на оси абсцисс;
• основание симметрично относительно начала координат;
• треугольник полностью лежит внутри каждого из измеренных сечений заготовки.

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

Первая строка входного файла содержит целое число K – количество измеренных сечений.

Далее следуют описания каждого из K сечений. В первой строке описания сечения содержится число N_K – количество звеньев ломаной. За ней следуют (N_K + 1) строк, каждая из которых содержит пару целых чисел x_i и y_i – координаты вершин ломаной сечения в порядке их следования.

Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более 10^–6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x – y| / max{1, |y|} не превышает 10^–6.

1 ≤ K ≤ 1000, сумма N_i ≤ 10⁵, координаты вершин по модулю не превышают 10⁹. 

Каждый тест для данной подзадачи оценивается отдельно.