
ZOJ Problem Set  2687
We have a robot and an obstacle in a 2dimensional plane. The robot is represented as a rectilinear square, and the obstacle as a rectilinear polygon. By rectilinear, we mean that the edges of a polygon are either horizontal or vertical. Initially, the robot is located outside the obstacle; that is, it does not intersect the boundary and is not in the interior of the obstacle. The robot wants to "escape" the obstacle by moving in horizontal or vertical directions without intersecting the obstacle. We say that the robot escapes the obstacle if it moves completely out of the smallest rectangle containing the obstacle (refer to Figure 1 and Figure 2). Note that the robot can be located outside of the smallest rectangle initially. You are to write a program for determining whether or not a robot can escape the obstacle. In Figure 1 the robot cannot escape the obstacle, but in Figure 2 it can escape the obstacle; R represents a robot and P represents an obstacle. Let (x, y) be the coordinate of a vertex of P. Both x and y are multiples of 10 and 10 <= x, y <= 1000000. The length of an edge of R is a natural number less than 1000000, and its lowest digit is always 2, e.g., 2, 12, 22, 32, etc. Input The input consists of T test cases. The number of test cases (T) is given on the first line of the input file. The first line of each test case contains 3 integers n_{x}, n_{y}, and w (2 <= n_{x}, n_{y}, w <= 1000000), where (n_{x}, n_{y}) is the coordinate of the leftbottom corner of the robot R and w is the length of an edge of R with the lowest digit of w being fixed to 2. The second line contains an integer n (4 <= n <= 1000), where n is the number of vertices of a rectilinear polygon P. The following n lines contain the coordinates of the vertices of P in counterclockwise order. Each line contains two integers nx and ny (10 <= n_{x}, n_{y} <= 1000000 and n_{x} and n_{y} are multiples of 10), where n_{x} is the xcoordinate and n_{y} is the ycoordinate of a vertex of P. A robot R is outside of P for every test case. Output For each test case, your program reports "YES" if the robot can escape the obstacle or "NO" otherwise. The following shows sample input and output for two test cases.Sample Input 2 30 30 12 12 10 10 90 10 90 60 80 60 80 20 20 20 20 70 50 70 50 50 70 50 70 90 10 90 200 200 52 12 450 500 100 500 100 100 450 100 450 250 350 250 350 150 150 150 150 300 250 300 250 400 Sample Output NO YES Source: Asia 2003, Seoul (South Korea) 