7-13 拯救007 (25分)
题目
在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）
设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。
输入格式：
首先第一行给出两个正整数：鳄鱼数量 N（≤100）和007一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的 (x,y) 坐标。注意：不会有两条鳄鱼待在同一个点上。
输出格式：
如果007有可能逃脱，就在一行中输出”Yes”，否则输出”No”。
输入样例 1：
1 | 14 20 |
2 | 25 -15 |
3 | -25 28 |
4 | 8 49 |
5 | 29 15 |
6 | -35 -2 |
7 | 5 28 |
8 | 27 -29 |
9 | -8 -28 |
10 | -20 -35 |
11 | -25 -20 |
12 | -13 29 |
13 | -30 15 |
14 | -35 40 |
15 | 12 12 |
输出样例1：
1 | Yes |
输入样例2：
1 | 4 13 |
2 | -12 12 |
3 | 12 12 |
4 | -12 -12 |
5 | 12 -12 |
输出样例2：
1 | No |
代码
1 | |
2 | using namespace std; |
3 | struct fun{ |
4 | int x,y; |
5 | }great[1000]; |
6 | int vis[1100]; |
7 | int n,m; |
8 | int flag=0; |
9 | int first(int i){ |
10 | int p1=great[i].x*great[i].x; |
11 | int p2=great[i].y*great[i].y; |
12 | int num=(m+7.5)*(m+7.5);//中心岛跳出 |
13 | if(p1+p2<=num){ |
14 | return 1; |
15 | } |
16 | return 0; |
17 | } |
18 | int key(int x){ |
19 | if(great[x].x-m<=-50||great[x].x+m>=50||great[x].y-m<=-50||great[x].y+m>=50) |
20 | return 1; |
21 | return 0; |
22 | } |
23 | int jump(int i,int j){//判断能不能跳到下个鳄鱼 |
24 | int p1=(great[i].x-great[j].x)*(great[i].x-great[j].x); |
25 | int p2=(great[i].y-great[j].y)*(great[i].y-great[j].y); |
26 | if(p1+p2<=m*m) |
27 | return 1 ; |
28 | return 0; |
29 | } |
30 | void dfs(int x){ |
31 | vis[x]=1; |
32 | if(key(x)){ //能直接出去 |
33 | flag=1; |
34 | return; |
35 | } |
36 | for(int i=0;i<n;i++){ |
37 | if(!vis[i]&&jump(x,i)){ |
38 | dfs(i); |
39 | } |
40 | } |
41 | } |
42 | int main(){ |
43 | scanf("%d %d",&n,&m); |
44 | for(int i=0;i<n;i++){ |
45 | scanf("%d %d",&great[i].x,&great[i].y); |
46 | } |
47 | if(m>=50){ |
48 | printf("Yes\n"); |
49 | } |
50 | else{ |
51 | memset(vis,0,sizeof(vis)); |
52 | for(int i=0;i<n;i++){ |
53 | if(!vis[i]&&first(i)){ //判断第一跳能不能直接出去 |
54 | dfs(i); |
55 | } |
56 | } |
57 | if(flag==1) |
58 | printf("Yes\n"); |
59 | else |
60 | printf("No\n"); |
61 | } |
62 | return 0; |
63 | } |