Wally World
Два влюбленных, которым не суждено быть вместе, хотят встретиться. Они находятся в разных точках на плоскости (но разве не все мы?). Они могут свободно перемещаться, за исключением того, что существует одна стена, которую нельзя пересечь. Стена представляет собой отрезок, параллельный либо оси x, либо оси y. Каждый из влюбленных может перемещаться на 1 единицу за 1 секунду. Сколько времени потребуется, чтобы они встретились, если оба выберут наилучший путь?
Входные данные
Ввод для каждого теста состоит из двух строк, каждая из которых содержит четыре целых числа. Первые два числа указывают координаты x и y первого влюбленного; следующие два числа указывают координаты x и y второго влюбленного. Следующие четыре числа указывают начальную и конечную точки стены. Более того, в каждом случае оба влюбленных не будут находиться на (бесконечной) прямой, содержащей стену, то есть, стену, продолженную в обоих направлениях. Все координаты будут положительными и не превышающими 10000, и ни один из влюбленных не начнет на стене.
Ввод будет завершен строкой, содержащей четыре нуля.
Выходные данные
Для каждого теста выведите минимальное время в секундах, за которое два влюбленных смогут встретиться. Выведите ответ с точностью до 3 десятичных знаков, используя формат вывода, показанный в примере.