Задача A. Треугольник на цилиндре

Автор:Dmitriy Merzlyakov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Заказчик выпускает 3-х мерный цилиндр единичного радиуса, на котором отмечены три точки, заданные в цилиндрических координатах i,zi), i = 1,2,3.

Юному программисту Васе поручено вырезать треугольник из цветной бумаги так, чтобы при наклеивании этого треугольника на цилиндр его вершины совпали с отмеченными точками, и чтобы такой треугольник не был наклеен сам на себя (при этом допускается пересечение по точкам или наличие общих сторон). Помимо этого такой треугольник должен быть невырожденным (иметь ненулевую площадь).

В дальнейшем, из этого цилиндра сделают развёртку путём разрезания цилиндра по любой прямой параллельной оси Z и разворачивания его на плоскость. Заказчик требует, чтобы любая такая прямая сечения пересекала этот треугольник не более 2-х раз.

Вася хочет минимизировать расход бумаги и поэтому собирается написать программу, которая по заданным 3 точкам на цилиндре определит наименьшую возможную площадь треугольника S > 0, который удовлетворяет всем указанным требованиям. Помогите Васе написать такую программу.

Формат входного файла

В i-ой (i = 1,2,3) строке содержатся числа ϕi,zi – координаты точек на цилиндре. При этом значения углов ϕi указаны в градусах.

Формат выходного файла

Выходной файл содержит одно число S – минимальную возможную площадь треугольника с точностью не менее 5-го знака после запятой. Если такой треугольник построить нельзя – выведите 0.

Ограничения

Все входные значения являются целыми.

 − 180 ≤ ϕi ≤ 180,

 − 104 ≤ zi ≤ 104.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
0 1
0 0
90 0
0.78540
2
45 4
45 0
-45 0
3.14159

Разбор

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

При этом связь между углом ϕ и ориентированной длиной соответствующей дуги для цилиндра единичного радиуса выражается как L(ϕ) = π180 ⋅ ϕ.

Площадь треугольника с вершинами в заданных точках i,zi) может быть найдена через псевдоскалярное произведение образующих его векторов: S = 12 ⋅ |L2 − ϕ1) ⋅ (z3 − z1) − L3 − ϕ1) ⋅ (z2 − z1)|.

Однако здесь также следует учитывать, что у нас имеет место периодичность по координате ϕ.

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

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

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

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

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


0.096s 0.010s 15