拯救007
在老电影“007之生死关头”(Live and Let Die)中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！(据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。)
设鳄鱼池是长宽为 $100$ 米的方形，中心坐标为 $(0, 0)$ ，且东北角坐标为 $(50, 50)$ 。池心岛是以 $(0, 0)$ 为圆心、直径 $15$ 米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。
输入格式:
首先第一行给出两个正整数: 鳄鱼数量 $N$ ($≤100$) 和007一次能跳跃的最大距离 $D$。随后 $N$ 行，每行给出一条鳄鱼的 $(x,y)$ 坐标。注意: 不会有两条鳄鱼待在同一个点上。
输出格式:
如果007有可能逃脱，就在一行中输出 Yes ，否则输出 No 。
输入样例1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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
|
输出样例1:
输入样例2:
1
2
3
4
5
| 4 13
-12 12
12 12
-12 -12
12 -12
|
输出样例2:
分析
这道题一个普遍的思路是建图然后去dfs或者bfs，但是我并不是这样做的(甚至没有建图)。我结合了贪心算法和动态规划的思想(可能也不沾边)，想出了一个我自认为绝妙的算法(也许并不绝妙)。
我们定义在这个100*100的方形内为 区域 ，而一切007能够跳到(无论能否站得住脚)的区域叫做 可达区域 。我们发现， 可达区域 是可被派生的，以任何包含在 可达区域 内的鳄鱼为圆心、以 $D$ 为半径的 区域 均为 可达区域 。这个性质，叫做 可达区域的派生性 (我瞎起的名字)。这个可被派生的性质，大概与动态规划中状态转移的原理类似。
既然可被派生，自然而然就出现了一个思路: 从起点出发，依次派生 可达区域 ，最后判断 可达区域 能不能碰到边界就行了。当然这个顺序应该不一定非得从起点到边界，我想从边界到起点也是完全可以的，代码中实现的是前者。
具体操作是: 将以起点为圆心， $D$ 为半径的圆内的所有鳄鱼标记为 可达 ，然后再以离起点最近的 可达 鳄鱼为起点，重复上述操作，直到某个鳄鱼的 可达区域 触碰到边界输出 Yes ，或到最后也没能触碰到边界输出 No 。每次选择离起点最近的可达鳄鱼这一点，或多或少使用了贪心算法的思想。当然因为最开始的起点本身是一个区域，所以可能需要做一下处理，把第一次的半径 $D$ 改为 $D+7.5$ 。为了方便寻找离起点最近的鳄鱼的操作，我在最开始写了一个冒泡排序。
AC代码
以下代码为了方便使用了C99的动态数组以及C++的重载与引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <stdio.h>
#include <math.h>
typedef struct {
int x, y;
} _point;
void swap(_point &p, _point &q) {_point temp = p; p = q; q = temp;}
int x2y2(_point src) {return src.x * src.x + src.y * src.y;}
int x2y2(_point src1, _point src2) {return (src1.x-src2.x) * (src1.x-src2.x) + (src1.y-src2.y) * (src1.y-src2.y);}
int main() {
int N, D, cmpd;
double cmpv;
scanf("%d %d", &N, &D);
_point point[N];
cmpd = 50-D;
bool arrive[N]={0};
for(int i=0; i<N; i++)
scanf("%d %d", &point[i].x, &point[i].y);
if(cmpd <= 0) {
printf("Yes\n");
return 0;
}
for(int i=0; i<N; i++)
for(int j=0; j<N-i-1; j++)
if(x2y2(point[j]) > x2y2(point[j+1]))
swap(point[j], point[j+1]);
cmpv = (D+7.5)*(D+7.5);
for(int i=0; i<N; i++) {
if(x2y2(point[i]) <= cmpv) {
arrive[i] = true;
if(abs(point[i].x) >= cmpd || abs(point[i].y) >= cmpd) {
printf("Yes\n");
return 0;
}
} else break;
}
cmpv = D * D;
for(int i=0; i<N; i++) {
if(arrive[i]) {
for(int j=0; j<N; j++) {
if(!arrive[j] && x2y2(point[i], point[j]) <= cmpv) {
arrive[j] = true;
if(abs(point[j].x) >= cmpd || abs(point[j].y) >= cmpd) {
printf("Yes\n");
return 0;
}
}
}
}
}
printf("No\n");
return 0;
}
|