Задача C. Шагающий циркуль ≡

Условие

Первоклассник нарисовал на бумаге две различные точки: A и B. Он воткнул ножку шагающего циркуля в точку A, другая ножка не касалась бумаги. Если он теперь воткнёт вторую ножку в произвольную точку плоскости, до которой дотягивается циркуль, а затем вытащит из бумаги первую ножку, то такое действие будет называться шагом циркуля.

Найти наименьшее количество шагов циркуля, которое нужно сделать, чтобы одна из его ножек оказалась в точке B. Раствор циркуля (т. е. длина шага) s может изменяться от s₁ до s₂ включительно (s₁ ≤ s ≤ s₂).

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

Первая строка содержит вещественные числа x_A y_A x_B y_B — координаты точек A и B.

Вторая строка содержит вещественные числа s₁ s₂.

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

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

Ограничения

 − 70 < x_A, y_A, x_B, y_B < 70,

1 ≤ s₁ ≤ s₂ < 100.

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

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

1 1.5 3 0.5
1.0 1.2

2

Разбор

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

Обозначим через D_i множество точек, до которых от точки A можно дойти за i шагов.

Множество D₀ состоит из одной единственной точки A.

D₁ — множество точек M таких, что s₁ ≤ AM ≤ s₂. Это кольцо с центром в точке A.

Что значит, что точка M принадлежит множеству D₂? Это значит, что существует точка N∈D₁ такая, что s₁ ≤ NM ≤ s₂, т.е. до точки N можно дойти из точки A за один шаг и из точки N можно шагнуть в точку M.

Геометрически D₂ — это объединение колец с центрами в точках множества D₁ и радиусами s₁ и s₂. Объединение всех этих колец образует круг с центром в точке A радиуса 2s₂.

Аналогично строятся множества D₃, D₄ и так далее. Множество D_i(i > 1) — это круг с центром в точке A радиуса i × s₂.

Определим множество с наименьшим номером, содержащее точку B. Если , то ответ — 1 шаг. Если , то нужно решить неравенство , поэтому ответ —  — наименьшее целое число, которое больше либо равно , или частное , округлённое вверх.

В случае, когда точка B лежит внутри круга с центром в A радиуса s₁, решив неравенство, мы получим 1 вместо 2, поэтому этот случай нужно рассмотреть отдельно.

Замечание. Траекторию движения циркуля можно легко построить с помощью циркуля и линейки.