1 #include<stdio.h> 2 #include<math.h> 3 #define MAXN 102 4 struct pos{ 5 int x,y; 6 }; 7 struct pos p[MAXN]; 8 int n,d,flag; 9 int g[MAXN][MAXN],vis[MAXN]; 10 double dis(struct pos p1,struct pos p2); 11 void read(); 12 void creatg(); 13 void dfs(int x); 14 int main(){ 15 flag=0; 16 read(); 17 creatg(); 18 dfs(0); 19 if(flag==1) printf("Yes\n"); 20 else printf("No\n"); 21 return 0; 22 } 23 void read(){ 24 int i; 25 scanf("%d %d",&n,&d); 26 for(i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y); 27 for(i=0;i<=n+1;i++) vis[i] = 0; 28 } 29 double dis(struct pos p1,struct pos p2){ 30 double t1 = pow((p1.x-p2.x),2) + pow((p1.y-p2.y),2); 31 return sqrt(t1); 32 } 33 void creatg(){ 34 int i,j; 35 struct pos o; 36 o.x = 0; 37 o.y = 0; 38 for(i=0;i<=n+1;i++) 39 for(j=0;j<=n+1;j++) 40 g[i][j] = 0; 41 42 for(i=1;i<=n;i++){ 43 if((dis(o,p[i])-15/2.0)<=d){ 44 //if((dis(o,p[i]))<=d){ 45 g[0][i] = 1; 46 g[i][0] = 1; 47 } 48 else { 49 g[0][i]=0; 50 g[i][0]=0; 51 } 52 53 if((50-abs(p[i].x))<=d || ((50-abs(p[i].y))<=d)) { 54 //可达 55 g[n+1][i] = 1; 56 g[i][n+1] = 1; 57 } 58 else{ 59 g[n+1][i]=0; 60 g[i][n+1]=0; 61 } 62 } 63 for(i=1;i<=n;i++){ 64 for(j=1;j<=n;j++){ 65 if(i==j){ 66 g[i][j] = 0; 67 g[j][i] = 0; 68 } 69 else{ 70 if(dis(p[i],p[j])<=d){ 71 g[i][j] = 1; 72 g[j][i] = 1; 73 } 74 else { 75 g[i][j] = 0; 76 g[j][i] = 0; 77 } 78 } 79 } 80 } 81 82 83 } 84 void dfs(int x){ 85 vis[x] = 1; 86 //printf("%d\n",x); 87 if(x==n+1) flag=1; 88 int i; 89 for(i=1;i<=n+1;i++){ 90 if(i!=x&&vis[i]==0&&g[x][i]!=0) dfs(i); 91 } 92 }View Code