编程介的小学生 2016-12-25 06:13 采纳率: 20.5%
浏览 933
已采纳

Mission Impossible 不可能的使命

Description

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
B X1 Y1 X2 Y2 ... XB YB
where 3 <= B <= 1000 is the number of border points, and each Xi Yi 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
N X1 Y1 X2 Y2 ... XN YN
where 1 <= N <= 1000 is the number of informers, and Xi Yi is the coordinate of the i-th informer. The third line describes the position and radius of the radars, in the format
M X1 Y1 R1 X2 Y2 R2 ... XM YM RM
where 1 <= M <= 30 is the number of radars, Xi Yi is the coordinate of the i-th radar, and Ri is the radius of the i-th radar. All the coordinates are integers 0 <= X, Y <= 1000. The radius of the radars are integers in the range 1 <= R <= 1000. A test case where B = N = M = 0 indicates the end of the input. This test case must not be processed.
Output

For each test case in the input, your program must produce one line containing either "Mission impossible" or "Contact informer K", where "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.
Sample 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
Sample Output

Mission impossible
Contact informer 3

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-28 15:38
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名