|
Posted on 2007-09-13 10:29 oyjpart 阅读(1502) 评论(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> 4 using namespace std; 5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 6 const int N = 21; 7 const double EPS = 1e-8f; 8 const double INF = 1e100; 9 const double PI = acos(-1.0); 10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 11 inline int dblcmp(double a, double b) { 12 if(fabs(a-b) < EPS) 13 return 0; 14 return a < b ? -1 : 1; 15 } 16![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 17 int D, n; 18 double x[N], y[N]; 19 double d[N]; 20 bool chk[N]; 21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 22 struct Node { 23 double a; 24 int id; 25 Node(){} 26 Node(int ii, double aa) { 27 a = aa; 28 id = ii; 29 } 30 }; 31![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 32 bool operator<(const Node& a, const Node& b) { 33 return dblcmp(d[a.id], d[b.id]) == 1; 34 } 35![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 36 double 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 47 void 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 76 printf("impossible\n"); 77 } 78![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 79 int main() { 80![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 81 freopen("t.in", "r", stdin); 82 // freopen("t.out", "w", stdout); 83![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
这个代码哪里错了呢? 思来想去想到可能是出现了下面这种情况 一个状态A进入队列 过了一会又一个状态通过其他路径到达A状态 并且耗费比前面一次少 这个代码的做法是直接把其送入PQ,由于修改了d[A], 所以希望这个节点能够浮上去(浮到正确的位置)。 但是Wrong Answer。 可能这个节点在向上浮的过程中遇到了前面这个A状态 于是就不往上浮了。但其实前面那个状态并没有修正本身的位置,所以导致了新的状态的位置出错。 所以还是改成了下面的代码 AC
1 #include <queue> 2 #include <stdio.h> 3 #include <math.h> 4 using namespace std; 5 const int N = 21; 6 const double EPS = 1e-8f; 7 const double INF = 1e100; 8 const double PI = acos(-1.0); 9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) inline int dblcmp(double a, double b) { 10 if(fabs(a-b) < EPS) 11 return 0; 12 return a < b ? -1 : 1; 13 } 14 int D, n; 15 double x[N], y[N]; 16 double d[N]; 17 bool chk[N]; 18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Node { 19 double a, dist; 20 int id; 21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) Node() {} 22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) Node(int ii, double aa, double dd) { 23 a = aa; id = ii; dist = dd; 24 } 25 }; 26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool operator<(const Node& a, const Node& b) { 27 if(dblcmp(a.dist, b.dist) == 1) 28 return true; 29 return false; 30 } 31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double 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 } 41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(id == n-1) { 58 printf("%.0lf\n", d[n-1]); 59 return; 60 } 61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < n; ++i) if(!chk[i]) { 62 double nowa; 63 double nowd = cal_dist(a, id, i, nowa); 64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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 } 72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() { 73 freopen("t.in", "r", stdin); 74 int i; 75![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|