转载

PAT Saving James Bond - Easy Version

Saving James Bond - Easy Version

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

funny problem 继续考察图的遍历我用了DFS 每个鳄鱼还有小岛都为顶点注意第一次从小岛跳出的时候还要加上小岛的半径7.5

下面给出AC代码每天AC一道题生活好滋味

 1 #include <stdio.h>  2 #include <math.h>  3 #include <stdlib.h>  4   5 int flag[150],flag1=0;  6 int D,N;  7 float r,dis;  8   9 typedef struct  10 { 11     int x; 12     int y; 13 }crocodile; 14 crocodile c[150]; 15 void DFS(int i) 16 { 17     r=D; 18     flag[i]=1; 19     if((50-abs(c[i].x))<=r ||(50-abs(c[i].y))<=r) 20     { 21         printf("Yes/n"); 22         flag1=1; 23         r=-1; 24         return; 25     }     26     int j; 27      28     for(j=1;j<=N;j++) 29     { 30          31         dis=sqrt((c[j].x-c[i].x)*(c[j].x-c[i].x)+(c[j].y-c[i].y)*(c[j].y-c[i].y)); 32         if(dis<=r && flag[j]!=1) 33         { 34             DFS(j); 35         } 36     } 37 } 38 main() 39 { 40     int i,j; 41     scanf("%d%d",&N,&D); 42      43     c[0].x=c[0].y=0; 44     for(i=1;i<=N;i++) 45         scanf("%d%d",&c[i].x,&c[i].y); 46     r=15.0/2+D; 47     i=0; 48     for(j=1;j<=N;j++) 49     { 50         dis=sqrt((c[j].x-c[i].x)*(c[j].x-c[i].x)+(c[j].y-c[i].y)*(c[j].y-c[i].y)); 51         if(dis<=r && flag[j]!=1) 52         { 53             DFS(j); 54             r=15.0/2+D; 55         }     56     }         57     if(flag1==0) 58         printf("No/n"); 59 }