题目链接:7-9 拯救007 (25 分)
AC代码:代码中有注释
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,d;
int vis[105];
bool flag;
struct Node{
int x,y;
}nodes[105];
//判断007跳到第i个鳄鱼上时,再跳一步能否到达岸上
bool lastJump(int i){
if((nodes[i].x+d>=50)||(nodes[i].x-d<=-50)||(nodes[i].y+d>=50)||(nodes[i].y-d<=-50))
{
return true;
}
return false;
}
//判断007能否从一个鳄鱼头上跳到另外一个鳄鱼头上
bool jumpSuccess(int a,int b){
int x1 = pow(nodes[a].x-nodes[b].x,2);
int x2 = pow(nodes[a].y-nodes[b].y,2);
if(x1+x2<=d*d){
return true;
}
return false;
}
//判断007第一步能否跳到第一只鳄鱼上
bool first(int t){
int x1 = pow(nodes[t].x,2);
int x2 = pow(nodes[t].y,2);
if(x1+x2<=((d+7.5)*(d+7.5))) return true;
return false;
}
int dfs(int t){
vis[t]=1;
if(lastJump(t)){
return flag=true;
}
for(int i=0;i<n;i++){
if(!vis[i]&&jumpSuccess(t,i)){
flag=dfs(i);
}
}
return flag;
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=0;i<n;i++)
{
scanf("%d%d",&nodes[i].x,&nodes[i].y);
}
if(d>=42.5)
{
printf("YES\n");
}
else{
for(int i=0;i<n;i++)
{
if(!vis[i]&&first(i)){
dfs(i);
}
}
if(flag){
printf("Yes\n");
}
else {
printf("No\n");
}
}
system("pause");
return 0;
}