147. Black-white king
time limit per test: 0.25
memory limit per test: 4096
input: standard input
output: standard output
On the chessboard of size NxN leaves only three figures. They are black king, white king and black-white king. The black-white king is very unusual chess piece for us, because it is invisible. Black and white kings decided to conclude a treaty against black-white king (they don't see it, but know that it is somewhere near at chessboard). To realize there plans black and white must meet face to face, what means that they must occupy two neighboring cells (generally each cell has 8 neighbors). The black-white king wants to prevent them from meeting. To do this he must intercept one of the kings before they'll meet, that is to attack one of the kings (make a move to it's cell). If the opponent will make a move on the cell of black-white king, nothing will happen (nobody kill anybody). Your task is to find out have the black-white king chances to win or not. Consider that white and black kings choose the one of the shortest ways to meet. Remember, that they don't see the black-white king. The black-white king also has a strategy: he moves in such a way, that none of the parts of his way can be shortened (for example, he cannot move by zigzag).
In the case of positive answer (i.e. if the probability of black-white king to win is nonzero) find the minimal number of moves necessary to probable victory. Otherwise find the minimal total number of moves of black and white kings necessary to meet. Remember the order of moves: white king, black king, and black-white king. Any king can move to any of the 8 adjacent cells.
First line of input data contains the natural number N (2<=N<=10^6). The second line contains two natural numbers P1, Q1 (0<P1,Q1<N+1) - coordinates of black king, third line contains P2, Q2 (0<P2,Q2<N+1) - coordinates of white king, forth line contains P3, Q3 (0<P3,Q3<N+1) - coordinates of black-white king. Positions of all kings are different.
Write to the first line word "YES" if the answer id positive, and "NO" - otherwise. To the second line write a single number - the numerical answer to the task.
|Author:||Michael R. Mirzayanov (Special thanks to S. Surganova and D. Arbenina)
|Resource:||Phisical Technical Lyceum #1 Trainings
|Server time: 2017-11-21 16:32:56||Online Contester Team © 2002 - 2016. All rights reserved.|