|
|
Posted on 2007-09-13 10:29 oyjpart 閱讀(1510) 評論(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
|