ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1767. Дом доктора Ди

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Мистер Икс очень любит роман «Дом доктора Ди», действие которого происходит в Лондоне в XVI и в конце XX века. В очередной раз перечитывая этот роман, Мистер Икс решил нарисовать карту Лондона с маршрутами движения главных героев книги — доктора Ди и Мэтью Палмера. Доктор Ди, живший в XVI веке, часто совершал путешествие от своего дома до Собора Святого Павла, а Мэтью, живший в XX веке, регулярно проделывал путь от Национальной галереи до Британского музея.
Каждый раз, когда герои романа оказывались в одной точке Лондона, у доктора Ди возникали видения, рассказывающие ему о том, что происходит в этот момент с Мэтью. Такие моменты случались довольно часто, поэтому Мистер Икс решил изобразить на карте Лондона траектории движения героев так, чтобы длина общей части этих траекторий была как можно больше. Но Мистер Икс не силён в топографии Лондона. Он считает, что город выстроен по прямоугольному плану — все улицы идут либо с запада на восток, либо с севера на юг, проходя через весь город от края до края. Дом доктора Ди, Собор Святого Павла, Национальная галерея и Британский музей располагаются в точности на пересечении двух перпендикулярных улиц. Кроме того, Мистер Икс уверен, что герои романа всегда перемещались по одному из кратчайших доступных им путей.
Несмотря на то, что Лондон поистине огромен, Мистер Икс уже нарисовал карту города. Затем он отметил на ней дом доктора Ди, Собор Святого Павла, Национальную галерею и Британский музей. Осталось лишь изобразить нужные маршруты.

Исходные данные

В первой строке через пробел записаны координаты дома доктора Ди. В следующих строках аналогичным образом заданы координаты Собора Святого Павла, Национальной галереи и Британского музея. Все координаты — целые числа, не превосходящие по модулю 109.

Результат

Выведите максимальную длину общей части траекторий движения доктора Ди и Мэтью Палмера.

Пример

исходные данныерезультат
2 2
4 4
5 5
3 3
2
Автор задачи: Алексей Самсонов
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.