Задачи
Message in the Enemy Territory
Message in the Enemy Territory
A group of commandos has been caught and sent to a maximum-security prison in enemy territory. In order to escape from the prison, a soldier needs to give a message to the squadron leader.
The boundary of the prison is protected by electronical arms: for his security, the soldier needs to keep a distance greater than \textbf{m} from the boundary. An additional restriction is that the soldier can only stand on those positions with integer coordinates. In each step, the soldier can move, from a given position (\textbf{x}; \textbf{y}), only to the nearby positions: (\textbf{x}-\textbf{1}; \textbf{y}-\textbf{1}), (\textbf{x}-\textbf{1}; \textbf{y}), (\textbf{x}-\textbf{1}; \textbf{y}+\textbf{1}), (\textbf{x}; \textbf{y}-\textbf{1}), (\textbf{x}; \textbf{y}+\textbf{1}), (\textbf{x}+\textbf{1}; \textbf{y}-\textbf{1}), (\textbf{x}+\textbf{1}; \textbf{y}) and (\textbf{x}+\textbf{1}; \textbf{y}+\textbf{1}), without going out of the interior of the prison. The walls of the prison form a simple polygon (no repeated vertices and no intersections between edges) and all of them are parallel to either the \textbf{x}-axis or the \textbf{y}-axis of a hypothetical coordinate system. The following fi gure shows a typical prison's plan:
\includegraphics{https://static.e-olymp.com/content/f1/f1f7313302b6d79d0abaf981a0b0681dc87c0016.jpg}
(\textbf{xs}; \textbf{ys}) and (\textbf{x1}; \textbf{y1}) corresponds to the position of the soldier and the squadron leader respectively. The gray area indicates those positions that are at distance less than or equal to m from the prison's boundary, i.e., the zone that the soldier cannot stand on.
A safe path is a sequence of pairs of integer coordinates, each one at a distance greater than m from the boundary of the prison, so that consecutive pairs are dierent and do not differ in more than one in each coordinate. In the depicted example, there is not a safe path from the soldier to the squadron leader.
Your task is to determine, for a given prison's plan, if there exists a safe path from the soldier position to the squadron leader position.
\InputFile
The problem input consists of several test cases. Each test case consists of three lines:
\begin{itemize}
\item The first line contains two integer numbers separated by blanks, \textbf{n} and \textbf{m}, with \textbf{4} ≤ \textbf{n} ≤ \textbf{1000} and \textbf{1} ≤ \textbf{m} ≤ \textbf{30}, indicating the number of the prison's boundary vertices and the alarm range respectively.
\item The second line contains a list of \textbf{2n} integer numbers, \textbf{x_1}, \textbf{y_1}, ..., \textbf{x_n}, \textbf{y_n}, separated by blanks: the list of vertices of a simple n-polygon that describes the boundary of the prison. \textbf{0} ≤ \textbf{x_i}, \textbf{y}_\{i \}≤ \textbf{1000}.
\item The last line contains four integer numbers separated by blanks, \textbf{x_s}, \textbf{y_s}, \textbf{x_1}, and \textbf{y_1}, indicating the position of the soldier and the position of the squadron leader ( \textbf{0} ≤ \textbf{x_s}, \textbf{y}_\{s \}≤ \textbf{1000}, \textbf{0} ≤ \textbf{x_1}, \textbf{y}_\{1 \}≤ \textbf{1000}).
\end{itemize}
The end of the input is indicated by a line with "\textbf{0 0}''.
\OutputFile
For each test case the output includes a line with the word "\textbf{Yes}" if there exists a path from the soldier to the squadron leader. Otherwise the word "\textbf{No}" must be printed.
Входные данные #1
4 1 0 0 0 5 5 5 5 0 2 2 3 3 8 3 0 16 0 6 4 6 4 0 12 0 12 10 8 10 8 16 4 12 8 4 0 0
Выходные данные #1
Yes No