Message in the Enemy Territory#779
A group of commandos has been captured and sent to a maximum-security prison in enemy territory. To escape, the soldier must deliver a message to the squadron leader.
The boundary of the prison is protected by electronic arms: for safety, the soldier must keep a distance greater than from the boundary. An additional restriction is that the soldier may only stand at positions with integer coordinates. In each step, the soldier may move, from a given position , only to adjacent positions: (x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y), (x+1, y+1), without leaving the interior of the prison. The walls of the prison form a simple polygon (without repeated vertices or edge intersections), and all edges are parallel to either the -axis or -axis of a hypothetical coordinate system. The following figure shows a typical prison plan:
(x_s, y_s) and (x_1, y_1) correspond to the positions of the soldier and the squadron leader, respectively. The grey area indicates those positions within a distance less than or equal to from the prison boundary, i.e., the area where the soldier cannot stand.
A safe path is a sequence of pairs of integer coordinates, each at a distance greater than from the prison boundary, such that consecutive pairs are different and do not differ by more than one in each coordinate. In the illustrated example, there is no safe path from the soldier to the squadron leader.
Your task is to determine, for a given prison plan, whether there is a safe path from the soldier's position to the squadron leader's position.
The input consists of several test cases. Each test case contains three lines:
The first line contains two integers and (4 \le n \le 1000, 1 \le m \le 30): the number of boundary vertices and the alarm range.
The second line contains integers, x_1, y_1, \ldots, x_n, y_n: the sequence of vertices of a simple polygon describing the boundary of the prison. 0 \le x_i, y_i \le 1000.
The last line contains four integers: x_s, y_s, x_1, y_1, indicating the soldier's and squadron leader's positions (0 \le x_s, y_s \le 1000, 0 \le x_1, y_1 \le 1000).
The end of the input is indicated by a line containing "0 0".
For each test case, print "Yes" if there is a path from the soldier to the squadron leader; otherwise, print "No".
Example 1