Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; /////////////////////////////////////////////////////////////////////////// const int MAX = 2007; int N, S, T; double PI; struct Point { double x, y, z; Point() {} Point(double _x, double _y, double _z): x(_x), y(_y), z(_z) {} Point operator-(const Point & p) const { return Point(x-p.x, y-p.y, z-p.z); } Point operator-() const { return Point(-x, -y, -z); } bool operator==(const Point & p) const { return EQ(x, p.x) && EQ(y, p.y) && EQ(z, p.z); } double sz() const { return sqrt(x*x+y*y+z*z); } void read() { scanf("%lf%lf%lf", &x, &y, &z); } }; double dot(const Point & p1, const Point & p2) { return p1.x*p2.x + p1.y * p2.y + p1.z * p2.z; } double angle(const Point & p1, const Point & p2, const Point & p3) { Point v1 = -(p1-p2), v2 = p3-p2; double angle = acos(dot(v1, v2) / v1.sz() / v2.sz()); return angle/PI*180.0; } vector<Point> points; vector<int> graph[MAX]; int get_index(const Point & p) { REP(i, points.size()) if (p == points[i]) return i; int index = points.size(); graph[index].clear(); points.push_back(p); return index; } double get_dist(int i, int j) { return (points[i]-points[j]).sz(); } double get_angle(int i, int j, int k) { return angle(points[i], points[j], points[k]); } int new_point() { Point p; p.read(); return get_index(p); } double dp[MAX][MAX]; // node / prev typedef priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > myq; myq manage; void update(int node, int prev, double val) { if (val < dp[node][prev]) { dp[node][prev] = val; manage.push(make_pair(val, node*MAX+prev)); } } int main() { PI = acos(-1.0); while (scanf("%d%d%d", &N, &S, &T) == 3) { points.clear(); int start = new_point(); int finish = new_point(); REP(i, N) { int a = new_point(); int b = new_point(); graph[a].push_back(b); graph[b].push_back(a); } if (start == finish) { printf("0.0000\n"); continue; } REP(i, points.size()) REP(j, points.size()) dp[i][j] = (i==start?0.0:1e12); manage = myq(); // go from start vertex REP(i, graph[start].size()) { int j = graph[start][i]; update(j, i, get_dist(i,j)/S); } // go from other vertices double res = 1e12; while (!manage.empty()) { pair<double, int> temp = manage.top(); manage.pop(); int node = temp.second/MAX, prev = temp.second%MAX; double d = temp.first; if (dp[node][prev] < d) continue; if (node == finish) { res = d; break; } REP(i, graph[node].size()) { int next = graph[node][i]; double d2 = d + get_dist(node, next)/S + get_angle(prev, node, next)/T; update(next, node, d2); } } printf("%.4lf\n", res); } return 0; }
--- c4.s1081.cteam052.cockchaf.cpp.0.cockchaf.cpp +++ c4.s1118.cteam052.cockchaf.cpp.0.cockchaf.cpp @@ -44,4 +44,9 @@ } + Point operator-() const + { + return Point(-x, -y, -z); + } + bool operator==(const Point & p) const { @@ -67,5 +72,5 @@ double angle(const Point & p1, const Point & p2, const Point & p3) { - Point v1 = p1-p2, v2 = p3-p2; + Point v1 = -(p1-p2), v2 = p3-p2; double angle = acos(dot(v1, v2) / v1.sz() / v2.sz()); return angle/PI*180.0; @@ -102,8 +107,5 @@ } -int step; -int visited[MAX][MAX]; double dp[MAX][MAX]; // node / prev - typedef priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > myq; myq manage; @@ -109,18 +111,11 @@ myq manage; -bool update(int node, int prev, double val) +void update(int node, int prev, double val) { - if (visited[node][prev] != step) - { - visited[node][prev] = step; - dp[node][prev] = 1e12; - } if (val < dp[node][prev]) { dp[node][prev] = val; manage.push(make_pair(val, node*MAX+prev)); - return true; } - return false; } @@ -131,6 +126,4 @@ while (scanf("%d%d%d", &N, &S, &T) == 3) { - ++step; - points.clear(); int start = new_point(); @@ -145,4 +138,7 @@ if (start == finish) { printf("0.0000\n"); continue; } + REP(i, points.size()) REP(j, points.size()) + dp[i][j] = (i==start?0.0:1e12); + manage = myq(); // go from start vertex