Source code for submission s1081

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.   bool operator==(const Point & p) const
  47.   {
  48.     return EQ(x, p.x) && EQ(y, p.y) && EQ(z, p.z);
  49.   }
  50.  
  51.   double sz() const
  52.   {
  53.     return sqrt(x*x+y*y+z*z);
  54.   }
  55.  
  56.   void read()
  57.   {
  58.     scanf("%lf%lf%lf", &x, &y, &z);
  59.   }
  60. };
  61.  
  62. double dot(const Point & p1, const Point & p2)
  63. {
  64.   return p1.x*p2.x + p1.y * p2.y + p1.z * p2.z;
  65. }
  66.  
  67. double angle(const Point & p1, const Point & p2, const Point & p3)
  68. {
  69.   Point v1 = p1-p2, v2 = p3-p2;
  70.   double angle = acos(dot(v1, v2) / v1.sz() / v2.sz());
  71.   return angle/PI*180.0;
  72. }
  73.  
  74. vector<Point> points;
  75. vector<int> graph[MAX];
  76. int get_index(const Point & p)
  77. {
  78.   REP(i, points.size())
  79.     if (p == points[i])
  80.       return i;
  81.   int index = points.size();
  82.   graph[index].clear();
  83.   points.push_back(p);
  84.   return index;
  85. }
  86.  
  87. double get_dist(int i, int j)
  88. {
  89.   return (points[i]-points[j]).sz();
  90. }
  91.  
  92. double get_angle(int i, int j, int k)
  93. {
  94.   return angle(points[i], points[j], points[k]);
  95. }
  96.  
  97. int new_point()
  98. {
  99.   Point p;
  100.   p.read();
  101.   return get_index(p);
  102. }
  103.  
  104. int step;
  105. int visited[MAX][MAX];
  106. double dp[MAX][MAX]; // node / prev
  107.  
  108. typedef priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > myq;
  109. myq manage;
  110.  
  111. bool update(int node, int prev, double val)
  112. {
  113.   if (visited[node][prev] != step)
  114.   {
  115.     visited[node][prev] = step;
  116.     dp[node][prev] = 1e12;
  117.   }
  118.   if (val < dp[node][prev])
  119.   {
  120.     dp[node][prev] = val;
  121.     manage.push(make_pair(val, node*MAX+prev));
  122.     return true;
  123.   }
  124.   return false;
  125. }
  126.  
  127. int main()
  128. {
  129.   PI = acos(-1.0);
  130.  
  131.   while (scanf("%d%d%d", &N, &S, &T) == 3)
  132.   {
  133.     ++step;
  134.  
  135.     points.clear();
  136.     int start = new_point();
  137.     int finish = new_point();
  138.     REP(i, N)
  139.     {
  140.       int a = new_point();
  141.       int b = new_point();
  142.       graph[a].push_back(b);
  143.       graph[b].push_back(a);
  144.     }
  145.     if (start == finish) { printf("0.0000\n"); continue; }
  146.  
  147.     manage = myq();
  148.     // go from start vertex
  149.     REP(i, graph[start].size())
  150.     {
  151.       int j = graph[start][i];
  152.       update(j, i, get_dist(i,j)/S);
  153.     }
  154.  
  155.     // go from other vertices
  156.     double res = 1e12;
  157.     while (!manage.empty())
  158.     {
  159.       pair<double, int> temp = manage.top();
  160.       manage.pop();
  161.       int node = temp.second/MAX, prev = temp.second%MAX;
  162.       double d = temp.first;
  163.       if (dp[node][prev] < d) continue;
  164.       if (node == finish)
  165.       {
  166. 	res = d;
  167. 	break;
  168.       }
  169.  
  170.       REP(i, graph[node].size())
  171.       {
  172. 	int next = graph[node][i];
  173. 	double d2 = d + get_dist(node, next)/S + get_angle(prev, node, next)/T;
  174. 	update(next, node, d2);
  175.       }
  176.     }
  177.     printf("%.4lf\n", res);
  178.   }
  179.  
  180.   return 0;
  181. }
  182.  

Diff to submission s1053

cockchaf.cpp

--- c4.s1053.cteam052.cockchaf.cpp.0.cockchaf.cpp
+++ c4.s1081.cteam052.cockchaf.cpp.0.cockchaf.cpp
@@ -134,12 +134,14 @@
     
     points.clear();
-    int start = new_point(), finish = new_point();
+    int start = new_point();
+    int finish = new_point();
     REP(i, N)
     {
-      int a = new_point(), b = new_point();
+      int a = new_point();
+      int b = new_point();
       graph[a].push_back(b);
       graph[b].push_back(a);
     }
-    if (start == finish) { printf("0\n"); continue; }
+    if (start == finish) { printf("0.0000\n"); continue; }
     
     manage = myq();