|
||||||||||
Shoot Your Gun!Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 89 Accepted Submission(s): 6 Problem Description There are two rectangular polygons (simple polygons with interior angles of only 90 or 270 degrees) G and T , inside another rectangular polygon M . You can place a gun anywhere on the boundary of G , then shoot a bullet in one of four diagonal directions, and then touch the boundary of T . You may shoot across an edge of T , but touching only a corner is also allowed. Your bullet is not allowed to touch G again (even touching a corner of G is not allowed), before touching T . The edges of M can reflect the bullet. When the bullet touches a vertex of M , it may simply go through it (and not regarded as a reflection), or go back. These special cases are shown in the figure above. Write a program to find the minimal number of reflections needed from G to T . Input The input contains several test cases. The first line of each case contains three positive integers nG, nT, nM (4<=nG, nT, nM<=50) . The next line contains nG pairs of integers, the coordinates (non-negative integers not greater than 4000) of the vertices of G , in counter-clockwise order. The next two lines describe polygon T and M , in the same format. It is guaranteed that G and T are outside each other (their boundaries will not touch), and are both inside M (they do not touch the boundary of M ). The last test case is followed by a single zero, which should not be processed. Output For each test case, print the case number and the minimal number of reflections to touch T . If it's impossible, output `-1'. Sample Input
Sample Output
Source | ||||||||||
|