本文主要是介绍05-2. Saving James Bond - Easy Version,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
需要注意的是1.能否从中心岛跳到其他顶点,需要计算(0,0)到顶点的距离再减去小岛半径
2.顶点到地点先把所有顶点转到到第一象限再判断方便一些
/* ***********************************************
Author :fisty
Created Time :2015/1/1 22:21:13
File Name :007.cpp
************************************************ */#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define MAX_N 110
int n, d;
pair<int, int> G[MAX_N];
int used[MAX_N];
bool jump1(int i){//可以从原点起跳到别的顶点//顶点到圆心的距离减去7.5int x = G[i].first;int y = G[i].second; if((sqrt((double)(x*x+y*y))-7.5) - (double)d < 1e-10)return true;return false;
}
bool jump2(int v, int w){//可以从顶点v跳到顶点wint x = (G[v].first - G[w].first);int y = (G[v].second - G[w].second);if(sqrt(double(x*x + y*y)) - (double)d < 1e-10)return true;return false;
}
bool can(int v){//可以逃离int x = abs(G[v].first);int y = abs(G[v].second);if((x + d >= 50) || (y + d >= 50))return true;return false;
}
bool dfs(int v){used[v] = 1;if(can(v)){//如果可以跳出池塘return true;}else{bool ans = false;for(int i = 0;i < n; i++){if(!used[i] && jump2(v, i)){//如果没有跳过并且可以跳到ans = dfs(i);if(ans) break;}}return ans;}
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin.tie(0);std::ios::sync_with_stdio(false);while(scanf("%d%d", &n, &d) != EOF){memset(used, 0 , sizeof(used)); for(int i = 0;i < n; i++){scanf("%d%d", &G[i].first, &G[i].second);}bool ans = false;for(int i = 0;i < n; i++){//枚举所有结点if(!used[i] && jump1(i)){//如果可以从原点出发,并且可以跳到空地ans = dfs(i);if(ans) break;}}if(ans)printf("Yes\n");elseprintf("No\n");}return 0;
}
这篇关于05-2. Saving James Bond - Easy Version的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!