|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
B - Mission Impossible
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
You have been hired to explore enemy territory. It is risky business, you know that. So, you’d better be prepared! The enemy has placed a number of security points all over his country, from which radars are detecting any moving vehicle within their range of cover. Any such detected object will be immediately destroyed. Fortunately enough, you have been given by your government a map of the enemy territory, consisting of coordinates and radius of coverage of each radar. You have also a list of local informers (together with their locations) that you should contact in order to obtain valuable information. Your mission is to try to contact one of these informers, preferably the one with highest insider-coefficient. The insider-coefficient of each informer is simply the distance from the informer to the border of the country, where such a distance is defined as the minimum over all distances from the location of the informer to each point of the border. In intuitive sense, the informer with highest insider-coefficient is that who is located as inside the country as possible, and will presumably have more valuable information about the country.
Your first thought is then to design a computer program which will check if there is a path from your initial location, always the point (2000, 2000), to any of the informers’ location, without crossing any region which is covered by radar. Whenever possible, the program should indicate which reachable informer is the one to be contacted, according to the insider-coefficient criteria described above.
The enemy country has the shape of a simple polygon (not necessarily convex). Recall that a polygon is called simple if it is described by a single, non-intersecting boundary. The borders of the country will be given as a sequence of $X,Y$-coordinates corresponding to the sequence of vertexes of the polygon. You may assume that all the radar’s centres and the informers’ coordinates are located within the country’s border. Notice, however, that the area covered by the radars might include regions outside the border.
In the sample scenario of Figure 1, informer $I1$ cannot be contacted since he is inside the region covered by radars. The informer $I2$, although outside the radar’s region, can’t be contacted either since any trip to his location would go through the deadly radar-covered regions. Both informers $I3$ and $I4$ could be contacted, so that informer $I4$ is chosen since his insider-coefficient is greater than that of $I3$.
Input
The input consists of several test cases. The first line of each test case describes the border of the enemy country, in the format
$\texttt{B X1 Y1 X2 Y2 ... XB YB}$
where $3 \leq B \leq 1000$ is the number of border points, and each $X_i$ $Y_i$ is the coordinate of the $i$-th point in the border. The border of the country consists of line segments between points $i$ and $i + 1$, and between points $B$ and $1$. The second line gives the number of informers and their respective positions, in the format
$\texttt{N X1 Y1 X2 Y2 ... XN YN}$
where $1 \leq N \leq 1000$ is the number of informers, and $X_i$ $Y_i$ is the coordinate of the $i$-th informer. The third line describes the position and radius of the radars, in the format
$\texttt{M X1 Y1 R1 X2 Y2 R2 ... XM YM RM}$
where $1 \leq M \leq 30$ is the number of radars, $X_i$ $Y_i$ is the coordinate of the $i$-th radar, and $R_i$ is the radius of the $i$-th radar. All the coordinates are integers $0 \leq X, Y \leq 1000$. The radius of the radars are integers in the range $1 \leq R \leq 1000$. A test case where $B = N = M = 0$ indicates the end of the input. This test case must not be processed.
The input must be read from standard input.
Output
For each test case in the input, your program must produce one line containing either $\texttt{“Mission impossible”}$ or $\texttt{“Contact informer K”}$, where $\texttt{K}$ is the index of the informer (as given in the input) with highest insider-coefficient which can be reached by the spy without going inside any radar coverage area. If there are more than one informer satisfying this condition, choose the one among them with lowest index.
The output must be written to standard output.
Sample test(s)
Input
4 0 0 0 200 200 200 200 0
2 70 70 120 120
1 100 100 100
4 0 0 0 200 200 200 200 0
3 100 102 70 80 20 10
4 70 70 35 130 70 35 130 130 35 70 130 35
0
0
0
Output
Mission impossible
Contact informer 3