ЗАДАЧА G
Фрукты
| Имя входного файла: | fruit.in |
| Имя выходного файла: | fruit.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Маленький узбекский Дед Морозик Куорбобо неожиданно вспомнил, что через час наступает Новый 2009 год, а он так и не приготовил никаких фруктов для праздничного стола. А ведь дома его ждет небольшая семья – любящая жена и 20 обожаемых детишек. Поэтому Куорбобо непременно должен собрать фрукты.
Домик Куорбобо находится посреди волшебного прямоугольного поля, протянувшегося на A метров с Востока на Запад и на B метров с Севера на Юг. Поле со всех сторон окружено фруктовыми деревьями, плодоносящими круглый год (не забывайте, что поле волшебное). А именно на Востоке поля растут мандарины, на Юге – апельсины, на Западе – яблоки, а на Севере – тыблоки (не удивляйтесь, это местный волшебный узбекский фрукт). Если считать, что Юго-Западный угол поля находится в начале координат, то дом Куорбобо находится в точке с координатами (X1,Y1), а сам Куорбобо стоит в точке (X0,Y0).
Поскольку семья у Куорбобо сравнительно маленькая, он хочет принести домой всего один мандарин, один апельсин, одно яблочко и одно тыблочко. Для этого ему нужно дойти до каждой из сторон поля, сорвать соответствующий фрукт и вернуться домой. При этом, если Куорбобо дойдет до угла поля, то он сможет сорвать сразу два фрукта.
Хоть зимы на волшебных полях Узбекистана и не очень холодные, Куорбобо все равно хочет попасть домой поскорей, а потому решил двигаться оптимальным образом. Помогите ему составить оптимальный маршрут и выведите его длину, а также координаты точек, где Куорбобо должен сорвать фрукты. Учтите, что Куорбобо может срывать фрукты в произвольном порядке, главное – сорвать по одному фрукту каждого вида.
Входные данные
В единственной строке входного файла записаны 6 целых чисел A, B, X0, Y0, X1, Y1 (2 ≤ A,B ≤ 200, 1 ≤ X0,X1 ≤ A-1, 1 ≤ Y0,Y1 ≤ B-1). Координаты начального положения Куобобо и его дома могут совпадать.
Выходные данные
В первую строку выведите длину оптимального маршрута Куорбобо. В каждой из следующих 4 строк выведите по 2 числа – координаты точек, где Куорбобо должен срывать фрукты: в первой строке – координаты точки для мандарина, во второй – апельсина, в третьей – яблока, в четвертой – тыблока. Все числа следует выводить с максимальной точностью. Значения будут сравниваться с точностью до 0.00001. Если существует несколько решений с минимальной длиной, выведите любое из них.
Пример
| fruit.in | fruit.out | Примечание |
|---|---|---|
|
|