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