首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7552

拯救007 在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱…

拯救007

在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去!(据说当年替身演员被最后一条鳄鱼咬住了脚,幸好穿的是特别加厚的靴子才逃过一劫。)

设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。

时间限制:6000

内存限制:262144

输入

首先第一行给出两个正整数:鳄鱼数量 N(≤ 100)和007一次能跳跃的最大距离 D。随后 N 行,每行给出一条鳄鱼的 (x, y) 坐标。注意:不会有两条鳄鱼待在同一个点上。

输出

如果007有可能逃脱,就在一行中输出"Yes",否则输出"No"。

样例输入

样例#1:

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

样例#2:

4 13
-12 12
12 12
-12 -12
12 -12

样例输出

样例#1:

Yes

样例#2:

No
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; using namespace std;   const int N = 110;   struct Node { int x, y; }; Node v[N];   int n, d; bool st[N], flag = false;   vector&lt;int&gt; firststep;   bool check(int a, int b) { int dx, dy; dx = pow(v[a].x - v[b].x, 2); dy = pow(v[a].y - v[b].y, 2); if (dx + dy &lt;= d * d) return true; return false; }   void DFS(int x) {   st[x] = true;   if (v[x].x - d &lt;= -50 || v[x].x + d &gt;= 50 || v[x].y - d &lt;= -50 || v[x].y + d &gt;= 50) { flag = true; return; }   for (int i = 0; i &lt; n; i++) { if (!st[i] &amp;&amp; check(x, i)) DFS(i); }   }   int main() {   cin &gt;&gt; n &gt;&gt; d;   for (int i = 0; i &lt; n; i++) {   int a, b; cin &gt;&gt; a &gt;&gt; b;   v[i].x = a, v[i].y = b;   if (pow(a, 2) + pow(b, 2) &lt;= pow(7.5 + d, 2)) firststep.push_back(i); }   if (d &gt;= 50) { puts("Yes"); return 0; }   for (int i = 0; i &lt; firststep.size(); i++) DFS(firststep[i]); if (flag) puts("Yes"); else puts("No");   return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; #include &lt;queue&gt; using namespace std; // 计算两点之间的距离 double distance(double x1, double y1, double x2, double y2) {     return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); } // 判断是否能从当前位置跳到岸边 bool canEscape(double x, double y, double D) {     return abs(x) &gt;= 50 - D || abs(y) &gt;= 50 - D; } // 判断能否从一个鳄鱼位置跳到另一个鳄鱼位置或岸边 bool canReach(double x1, double y1, double x2, double y2, double D) {     return distance(x1, y1, x2, y2) &lt;= D; } // 广度优先搜索判断是否能逃出生天 bool bfs(int N, double D, vector&lt;pair&lt;double, double&gt;&gt;&amp; crocodiles) {     vector&lt;bool&gt; visited(N, false);     queue&lt;int&gt; q;     // 先将起始位置(小岛)加入队列     q.push(0);     while (!q.empty()) {         int cur = q.front();         q.pop();         if (!visited[cur]) {             visited[cur] = true;             // 判断当前位置能否直接跳到岸边             if (cur == 0) {                 for (int i = 0; i &lt; N; ++i) {                     if (canReach(0, 0, crocodiles[i].first, crocodiles[i].second, D)) {                         q.push(i);                     }                 }             } else {                 if (canEscape(crocodiles[cur].first, crocodiles[cur].second, D)) {                     return true;                 }                 // 尝试跳到其他鳄鱼位置                 for (int i = 0; i &lt; N; ++i) {                     if (!visited[i] &amp;&amp; canReach(crocodiles[cur].first, crocodiles[cur].second, crocodiles[i].first, crocodiles[i].second, D)) {                         q.push(i);                     }                 }             }         }     }     return false; } int main() {     int N;     double D;     cin &gt;&gt; N &gt;&gt; D;     vector&lt;pair&lt;double, double&gt;&gt; crocodiles(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; crocodiles[i].first &gt;&gt; crocodiles[i].second;     }     if (bfs(N, D, crocodiles)) {         cout &lt;&lt; "Yes" &lt;&lt; endl;     } else {         cout &lt;&lt; "No" &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。