147. Blackwhite king
time limit per test: 0.25
sec.
memory limit per test: 4096
KB
input: standard input
output: standard output
On the chessboard of size NxN leaves only three figures. They are black king, white king and blackwhite king. The blackwhite king is very unusual chess piece for us, because it is invisible. Black and white kings decided to conclude a treaty against blackwhite 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 blackwhite 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 blackwhite king, nothing will happen (nobody kill anybody). Your task is to find out have the blackwhite 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 blackwhite king. The blackwhite 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 blackwhite 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 blackwhite king. Any king can move to any of the 8 adjacent cells.
Input
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 blackwhite king. Positions of all kings are different.
Output
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.
Sample test(s)
Input
5
1 1
5 3
2 3
Output
YES
1
Author:  Michael R. Mirzayanov (Special thanks to S. Surganova and D. Arbenina)

Resource:  Phisical Technical Lyceum #1 Trainings

Date:  Fall, 2002

Server time: 20170925 22:37:06  Online Contester Team © 2002  2016. All rights reserved. 

