|
|
Posted on 2007-09-13 10:29 oyjpart 阅读(1504) 评论(0) 编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
好久没贴题了。 贴个吧。
Robot
Time Limit:1000MS Memory Limit:65536K
Total Submit:590 Accepted:208
Description
Let (x1, y1), …, (xn, yn) be a collection of n points in a two-dimensional plane. Your goal is to navigate a robot from point (x1, y1) to point (xn, yn). From any point (xi, yi), the robot may travel to any other point (xj, yj) at most R units away at a speed of 1 unit per second. Before it does this, however, the robot must turn until it faces (xj, yj); this turning occurs at a rate of 1 degree per second.
Compute the shortest time needed for the robot to travel from point (x1, y1) to (xn, yn). Assume that the robot initially faces (xn, yn). To prevent floating-point precision issues, you should use the double data type instead of float. It is guaranteed that the unrounded shortest time will be no more than 0.4 away from the closest integer. Also, if you decide to use inverse trigonometric functions in your solution (hint, hint!), try atan2() rather than acos() or asin().
Input
The input test file will contain multiple test cases. Each test case will begin with a single line containing an integer R, the maximum distance between points that the robot is allowed to travel (where 10 ≤ R ≤ 1000), and an integer n, the number of points (where 2 ≤ n ≤ 20). The next n lines each contain 2 integer values; here, the ith line contains xi and yi (where −1000 ≤ xi, yi ≤ 1000). Each of the points is guaranteed to be unique. The end-of-file is denoted by a test case with R = n = −1.
Output
The output test file should contain a single line per test case indicating the shortest possible time in second (rounded to the nearest integer) required for the robot to travel from (x1, y1) to (xn, yn). If no trip is possible, print “impossible” instead.
Sample Input
10 2
0 0
7 0
10 3
0 0
7 0
14 5
10 3
0 0
7 0
14 10
-1 -1
Sample Output
7
71
impossible
Source
Stanford Local 2006
注意：下面这个代码是Wrong Answer的代码：
1 #include <queue>
2#include <stdio.h>
3#include <math.h>
4using namespace std;
5
6const int N = 21;
7const double EPS = 1e-8f;
8const double INF = 1e100;
9const double PI = acos(-1.0);
10
11inline int dblcmp(double a, double b) {
12 if(fabs(a-b) < EPS)
13 return 0;
14 return a < b ? -1 : 1;
15}
16
17int D, n;
18double x[N], y[N];
19double d[N];
20bool chk[N];
21
22struct Node {
23 double a;
24 int id;
25 Node(){}
26 Node(int ii, double aa) {
27 a = aa;
28 id = ii;
29 }
30};
31
32bool operator<(const Node& a, const Node& b) {
33 return dblcmp(d[a.id], d[b.id]) == 1;
34}
35
36double cal_dist(double agl, int a, int b, double& old) {
37 old = atan2(y[b]-y[a], x[b]-x[a]);
38 double now = fabs(old-agl);
39 double now2 = 2*PI-fabs(old-agl);
40 if(now2 < now) now = now2;
41 double dist = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
42 if(dblcmp(dist, D) == 1)
43 return INF;
44 return now * 180.0/PI + dist;
45}
46
47void solve() {
48 int i;
49 priority_queue<Node> PQ;
50 memset(chk, 0, sizeof(chk));
51 double a = atan2(y[n-1]-y[0], x[n-1]-x[0]);
52 PQ.push(Node(0, a));
53 d[0] = 0;
54 for(i = 1; i < n; ++i)
55 d[i] = INF;
56 while(!PQ.empty()) {
57 double a = PQ.top().a;
58 int id = PQ.top().id;
59 PQ.pop();
60 if(chk[id]) continue;
61 chk[id] = 1;
62 if(id == n-1) {
63 printf("%.0lf\n", d[n-1]);
64 return;
65 }
66 for(i = 0; i < n; ++i) if(!chk[i]) {
67 double nowa;
68 double nowd = cal_dist(a, id, i, nowa);
69 if(dblcmp(nowd+d[id], d[i]) == -1) {
70 d[i] = nowd+d[id];
71 PQ.push(Node(i, nowa));
72 }
73 }
74 }
75
76 printf("impossible\n");
77}
78
79int main() {
80
81 freopen("t.in", "r", stdin);
82// freopen("t.out", "w", stdout);
83
84 int i;
85 while(scanf("%d %d", &D, &n), !(D==-1 && n==-1)) {
86 for(i = 0; i < n; ++i)
87 scanf("%lf%lf", &x[i], &y[i]);
88 solve();
89 }
90 return 0;
91}
92
这个代码哪里错了呢？ 思来想去想到可能是出现了下面这种情况 一个状态A进入队列 过了一会又一个状态通过其他路径到达A状态 并且耗费比前面一次少 这个代码的做法是直接把其送入PQ，由于修改了d[A], 所以希望这个节点能够浮上去（浮到正确的位置）。 但是Wrong Answer。 可能这个节点在向上浮的过程中遇到了前面这个A状态 于是就不往上浮了。但其实前面那个状态并没有修正本身的位置，所以导致了新的状态的位置出错。 所以还是改成了下面的代码 AC
1#include <queue>
2#include <stdio.h>
3#include <math.h>
4using namespace std;
5const int N = 21;
6const double EPS = 1e-8f;
7const double INF = 1e100;
8const double PI = acos(-1.0);
9  inline int dblcmp(double a, double b)  {
10 if(fabs(a-b) < EPS)
11 return 0;
12 return a < b ? -1 : 1;
13 }
14int D, n;
15double x[N], y[N];
16double d[N];
17bool chk[N];
18struct Node {
19 double a, dist;
20 int id;
21  Node(){}
22 Node(int ii, double aa, double dd) {
23 a = aa; id = ii; dist = dd;
24 }
25};
26bool operator<(const Node& a, const Node& b) {
27 if(dblcmp(a.dist, b.dist) == 1)
28 return true;
29 return false;
30}
31double cal_dist(double agl, int a, int b, double& old) {
32 old = atan2(y[b]-y[a], x[b]-x[a]);
33 double now = fabs(old-agl);
34 double now2 = 2*PI-fabs(old-agl);
35 if(now2 < now) now = now2;
36 double dist = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
37 if(dblcmp(dist, D) == 1)
38 return INF;
39 return now * 180.0/PI + dist;
40}
41void solve() {
42 int i;
43 priority_queue<Node> PQ;
44 memset(chk, 0, sizeof(chk));
45 double a = atan2(y[n-1]-y[0], x[n-1]-x[0]);
46 PQ.push(Node(0, a, 0));
47 d[0] = 0;
48 for(i = 1; i < n; ++i)
49 d[i] = INF;
50 while(!PQ.empty()) {
51 double a = PQ.top().a;
52 int id = PQ.top().id;
53 double dist = PQ.top().dist;
54 PQ.pop();
55 if(chk[id]) continue;
56 chk[id] = 1;
57 if(id == n-1) {
58 printf("%.0lf\n", d[n-1]);
59 return;
60 }
61 for(i = 0; i < n; ++i) if(!chk[i]) {
62 double nowa;
63 double nowd = cal_dist(a, id, i, nowa);
64 if(dblcmp(nowd+d[id], d[i]) == -1) {
65 d[i] = nowd+d[id];
66 PQ.push(Node(i, nowa, nowd+d[id]));
67 }
68 }
69 }
70 printf("impossible\n");
71}
72int main() {
73 freopen("t.in", "r", stdin);
74 int i;
75 while(scanf("%d %d", &D, &n), !(D==-1 && n==-1)) {
76 for(i = 0; i < n; ++i)
77 scanf("%lf%lf", &x[i], &y[i]);
78 solve();
79 }
80 return 0;
81}
82
|