Тернарный поиск

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

 

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

 

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

 

Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 10⁴ ).

 

Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x₁, y₁, x₂ и y₂ и представляет собой прямую, проходящую через точки (x₁, y₁)  и (x₂, y₂) . Координаты заданных точек не превышают по модулю 10⁴. Точки (x₁ , y₁)  и (x₂ , y₂)  ни для какой прямой не совпадают.

 

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 10⁹, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.

 

Ответ должен иметь абсолютную или относительную погрешность не более 10⁻⁶, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10⁻⁶.

 

 

Ввод	Вывод
4 0 0 0 1 0 0 1 0 1 1 2 1 1 1 1 2	0.5000000004656613 0.4999999995343387
7 376 -9811 376 -4207 6930 -3493 6930 -8337 1963 -251 1963 -5008 -1055 9990 -684 9990 3775 -348 3775 1336 7706 -2550 7706 -8412 -9589 8339 -4875 8339	4040.9996151750674 12003.999615175067

 

Входной файл содержит 12 чисел: x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄, v_1x, v_1y, v_2x, v_2y. Координаты вершин первого отрезка: (x₁, y₁) и (x₂, y₂), координаты вершин второго отрезка: (x₃, y₃) и (x₄, y₄), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

 

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10⁻⁴. Если веточки не соприкоснутся никогда, выведите число -1.
 

Ввод	Вывод
0 0 -1 3 4 4 7 7 3 0 0 -1	1.6
0 0 -1 3 4 4 7 7 1 0 0 -3	-1

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ. 

 

Движение точки M можно задать с помощью ряда параметров:

 

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

 

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

 

• начального расстояния R от точки M до начала координат (точки O);

 

• скорости движения V точки M по лучу OK.

 

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

 

Требуется написать программу, которая найдет искомый прямоугольник

 

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

 

В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.

 

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.