06-圖2 Saving James Bond - Easy Version（25 分） （資料結構）

06-圖2 Saving James Bond - Easy Version（25 分）

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

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.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integersN (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:

For each test case, print in a line "Yes" if James can escape, or "No" if not.

題目大意

在一個二維坐标中有一個邊長為100米的正方形地圖，007位于坐标為原點啥上的圓形島上（島的直徑（diameter）為15），周圍全是鳄魚(點），他每次可跳D米，問你007可以逃出這個地圖嗎? 以案例為例詳情如下圖。

解題思路：把每個點的坐标存下來，然後進行dfs.

注意：第一跳和以後在鳄魚身上的跳是不一樣的。

詳細見代碼

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int BORDER=50;
const double  ISLAND=15.0/2;
const int N=110;
struct node{
	double x,y;
};
node p[N];//記錄鳄魚的坐标 
bool vis[N];//标記重複 
int n;//輸入鳄魚的個數 
double JUMP;//007每次可以調的距離 
bool FirstJump(int i){//第一次跳是否可以調到鳄魚身上 
	return sqrt( p[i].x*p[i].x+p[i].y*p[i].y )<=JUMP+ISLAND;
}
bool Jump(int x,int y){//每一次跳（除第一次）是否可以到鳄魚上 
	return sqrt( (p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)* ( p[x].y-p[y].y) )<=JUMP;
}
bool judge(int i){//判斷007是否逃出 
	return (abs(p[i].x)>=50-JUMP||abs(p[i].y)>=50-JUMP);
}
bool DFS(int i){
	vis[i]=true;
	bool ans=false;
	if(judge(i))
		return true;
	for(int t=0;t<n;t++)
	{
		if(!vis[t]&&Jump(i,t))
			ans=DFS(t);
		if(ans)
			break;
	}
	return ans;
}
void Save007(){
	bool IsSave=false;
	for(int i=0;i<n;i++){//周遊每一點，把每種情況dfs一遍 
		if(!vis[i]&&FirstJump(i)){		
			IsSave=DFS(i);//如果其中有其中情況符合要求，直接退出 
			if(IsSave)
				break;	
		}
	}
	if(IsSave)
		puts("Yes");
	else 
		puts("No");
}
int main()
{
	
	cin>>n>>JUMP;
	for(int i=0;i<n;i++)
		cin>>p[i].x>>p[i].y;
	for(int i=0;i<110;i++)
		vis[i]=false;
	 Save007();
	return 0;
}