#1109

Мост

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, ВКОШП, 2008, Задача B ]

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

Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки (x1,1,y1,1), продолжается отрезками (x1,1,y1,1) − (x1,2,y1,2), (x1,2,y1,2)− (x1,3,y1,3), ..., (x1,m−1,y1,m−1) − (x1,m,y1,m) и заканчивается лучом, направленным на север из точки (x1,m,y,m).

Аналогично, правый берег реки начинается лучом, направленным на юг из точки (x2,1,y2,1), продолжается отрезками (x2,1,y2,1) − (x2,2,y2,2), (x2,2,y2,2) − (x2,3,y2,3), ..., (x2,n−1,y2,n−1) − (x2,n,y2,n) и заканчивается лучом, направленным на север из точки (x2,n,y2).

Помогите руководству Флатландии выяснить, мост какой минимальной длины можно построить.

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

Первая строка входного файла содержит целое число m (2 ≤ m ≤ 100). Следующие m строк содержат по два целых числа координаты вершин ломаной левого берега: x1,1, y1,1, x1,2,y1,2, ...,x1,m, y1,m.

Следующая строка входного файла содержит целое число n (2 ≤ n ≤ 100). Следующие n строк содержат по два целых числа координаты вершин ломаной правого берега: x2,1, y2,1, x2,2, y2,2, ..., x2,n, y2,n.

Известно, что x1,1 < x2,1, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят 10⁴по абсолютной величине

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

Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью 10⁻^5.

Оптимальное положение моста показано на следующем рисунке:

Примеры

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

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

1.4142135623730951

#1128

Куда идем мы с Пяточком?

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Кировские командные турниры, 2001, Задача A ]

На плоскости есть непроходимый круг. Необходимо найти кратчайший путь от точки до точки.

«Кто ходит в гости по утрам, тот поступает мудро…»

Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем.

К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

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

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

Во входном файле записаны сначала координаты домика Винни-Пуха X_В Y_В, затем — координаты домика Кролика X_К Y_К, а затем — координаты центра и радиус ловушки X_Л Y_Л R_Л. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

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

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.

Примеры

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

0 0 10 0
5 5 1

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

10.000

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

3 4 4 4
0 0 5

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

1.000

#1189

Посчитайте лампы

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2007, Лига А, Задача G ]

На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.

На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.

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

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

Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.

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

В выходной файл выведите одно число — ответ задачи.

Примеры

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

2 20 4 5 1

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

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

4 20 4 5 2

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

#1244

Дремучий лес

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача H ]

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

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

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

Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

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

В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.

Примеры

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

3
      0.00      30.00      25.00
      0.00     -30.00      25.00
     40.00       0.00      16.00

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

NO
     -833.3333340000      -552.7707973875
      833.3333340000       552.7707973875

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

3
      0.00      30.00      29.00
      0.00     -30.00      29.00
     40.00       0.00      19.00

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

YES

#1617

Стройка

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига А, Задача B ]

На территории будущей стройки растут три дерева. Фирма получила разрешение на строительные работы с условием, что два (любых) дерева будут сохранены. Прораб хочет построить забор треугольной формы так, чтобы внутри него оказалось ровно два дерева.

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

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

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

Вводится информация о трех деревьях: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус – натуральное число.

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

Выведите одно число – номер дерева (деревья нумеруются начиная с 1 в порядке задания их во входных данных), которое окажется не огорожено. Если забор треугольной формы, огораживающий ровно два дерева, построить невозможно, выведите число 0. Если существует несколько решений, выведите любое.