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