0184. Чёрно-белый король

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	250 ms
Ограничение по памяти:	16 megabytes

На шахматной доске NхN осталось три фигуры. Черный король, белый и черно-белый. Для нас черно-белый король непривычная фигура, так как он невидимый. Черный и белый король решили заключить договор и объединиться против черно-белого (они его не видят, но знают, что он где-то рядом, на доске). Для того, что бы реализовать задуманное им необходимо встретиться, что значит оказаться на соседних клетках (в общем случае у каждой клетки 8 соседей). Черно-белый король хочет им помешать. Для этого он должен перехватить одного из королей до того, как они встретятся, то есть атаковать его (пойти на клетку противника). Если противник сходит на клетку черно-белого короля ничего страшного не произойдет (никто никого не ⌠убьет■). Ваша задача узнать, есть ли у него шансы на победу. Учтите, что черным и белым королем была выработана стратегия, в соответствии с которой, они выбрали один из кратчайших путей. Помните, что они не видят черно-белого короля. У черно-белого короля тоже есть стратегия: он всегда передвигается так, что любой отрезок его пути нельзя улучшить по длине (скажем зигзагами он ходить не может).

В случае положительного ответа (то есть при ненулевой вероятности победы черно-белого короля) найдите наименьшее число ходов, необходимымых для вероятной победы. Иначе выведите наименьшее суммарное количество ходов белого и черного короля необходимых для встречи. Помните порядок ходов: белый король, черный, черно-белый. Любой король ходит на одну из 8 соседних клеток.

Замечание: длиной пути короля здесь называем сделанное количество ходов.

Формат входного файла

В первой строке записано число N (2 ≤ N ≤ 10⁶). Во второй строке пара чисел P1, Q1 (0 < P1,Q1 < N+1) - координаты черного короля, в третьей записаны P2, Q2 (0 < P2,Q2 < N+1) - координаты белого короля. В четвертой строке парой чисел P3, Q3 (0 < P3,Q3 < N+1) задана позиция черно-белого короля. Все позиции различны.

Формат выходного файла

Выведите в первой строке "YES" если ответ положителен и "NO" в противном случае. Во второй строке выведите число, количественный ответ поставленной задачи.

Пример:

input.txt	output.txt
5 1 1 5 3 2 3	YES 1

Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Обсудить       Отправить решение



Версия для печати