Source code for submission s1118

Go to diff to previous submission

cockchaf.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int MAX = 2007;
  31. int N, S, T;
  32. double PI;
  33.  
  34. struct Point
  35. {
  36.   double x, y, z;
  37.   Point() {}
  38.   Point(double _x, double _y, double _z):
  39.     x(_x), y(_y), z(_z) {}
  40.  
  41.   Point operator-(const Point & p) const
  42.   {
  43.     return Point(x-p.x, y-p.y, z-p.z);
  44.   }
  45.  
  46.   Point operator-() const
  47.   {
  48.     return Point(-x, -y, -z);
  49.   }
  50.  
  51.   bool operator==(const Point & p) const
  52.   {
  53.     return EQ(x, p.x) && EQ(y, p.y) && EQ(z, p.z);
  54.   }
  55.  
  56.   double sz() const
  57.   {
  58.     return sqrt(x*x+y*y+z*z);
  59.   }
  60.  
  61.   void read()
  62.   {
  63.     scanf("%lf%lf%lf", &x, &y, &z);
  64.   }
  65. };
  66.  
  67. double dot(const Point & p1, const Point & p2)
  68. {
  69.   return p1.x*p2.x + p1.y * p2.y + p1.z * p2.z;
  70. }
  71.  
  72. double angle(const Point & p1, const Point & p2, const Point & p3)
  73. {
  74.   Point v1 = -(p1-p2), v2 = p3-p2;
  75.   double angle = acos(dot(v1, v2) / v1.sz() / v2.sz());
  76.   return angle/PI*180.0;
  77. }
  78.  
  79. vector<Point> points;
  80. vector<int> graph[MAX];
  81. int get_index(const Point & p)
  82. {
  83.   REP(i, points.size())
  84.     if (p == points[i])
  85.       return i;
  86.   int index = points.size();
  87.   graph[index].clear();
  88.   points.push_back(p);
  89.   return index;
  90. }
  91.  
  92. double get_dist(int i, int j)
  93. {
  94.   return (points[i]-points[j]).sz();
  95. }
  96.  
  97. double get_angle(int i, int j, int k)
  98. {
  99.   return angle(points[i], points[j], points[k]);
  100. }
  101.  
  102. int new_point()
  103. {
  104.   Point p;
  105.   p.read();
  106.   return get_index(p);
  107. }
  108.  
  109. double dp[MAX][MAX]; // node / prev
  110. typedef priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > myq;
  111. myq manage;
  112.  
  113. void update(int node, int prev, double val)
  114. {
  115.   if (val < dp[node][prev])
  116.   {
  117.     dp[node][prev] = val;
  118.     manage.push(make_pair(val, node*MAX+prev));
  119.   }
  120. }
  121.  
  122. int main()
  123. {
  124.   PI = acos(-1.0);
  125.  
  126.   while (scanf("%d%d%d", &N, &S, &T) == 3)
  127.   {
  128.     points.clear();
  129.     int start = new_point();
  130.     int finish = new_point();
  131.     REP(i, N)
  132.     {
  133.       int a = new_point();
  134.       int b = new_point();
  135.       graph[a].push_back(b);
  136.       graph[b].push_back(a);
  137.     }
  138.     if (start == finish) { printf("0.0000\n"); continue; }
  139.  
  140.     REP(i, points.size()) REP(j, points.size())
  141.       dp[i][j] = (i==start?0.0:1e12);
  142.  
  143.     manage = myq();
  144.     // go from start vertex
  145.     REP(i, graph[start].size())
  146.     {
  147.       int j = graph[start][i];
  148.       update(j, i, get_dist(i,j)/S);
  149.     }
  150.  
  151.     // go from other vertices
  152.     double res = 1e12;
  153.     while (!manage.empty())
  154.     {
  155.       pair<double, int> temp = manage.top();
  156.       manage.pop();
  157.       int node = temp.second/MAX, prev = temp.second%MAX;
  158.       double d = temp.first;
  159.       if (dp[node][prev] < d) continue;
  160.       if (node == finish)
  161.       {
  162. 	res = d;
  163. 	break;
  164.       }
  165.  
  166.       REP(i, graph[node].size())
  167.       {
  168. 	int next = graph[node][i];
  169. 	double d2 = d + get_dist(node, next)/S + get_angle(prev, node, next)/T;
  170. 	update(next, node, d2);
  171.       }
  172.     }
  173.     printf("%.4lf\n", res);
  174.   }
  175.  
  176.   return 0;
  177. }
  178.  

Diff to submission s1081

cockchaf.cpp

--- 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