Source code for submission s1163

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

Diff to submission s1118

cockchaf.cpp

--- c4.s1118.cteam052.cockchaf.cpp.0.cockchaf.cpp
+++ c4.s1163.cteam052.cockchaf.cpp.0.cockchaf.cpp
@@ -29,4 +29,5 @@
 
 const int MAX = 2007;
+const double FINF = 1e20;
 int N, S, T;
 double PI;
@@ -44,9 +45,4 @@
   }
   
-  Point operator-() const
-  {
-    return Point(-x, -y, -z);
-  }
-  
   bool operator==(const Point & p) const
   {
@@ -67,10 +63,10 @@
 double dot(const Point & p1, const Point & p2)
 {
-  return p1.x*p2.x + p1.y * p2.y + p1.z * p2.z;
+  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;
+  Point v1 = p2-p1, v2 = p3-p2;
   double angle = acos(dot(v1, v2) / v1.sz() / v2.sz());
   return angle/PI*180.0;
@@ -108,5 +104,5 @@
 
 double dp[MAX][MAX]; // node / prev
-typedef priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > myq;
+typedef priority_queue<pair<double, pair<int, int> >, vector<pair<double, pair<int, int> > >, greater<pair<double, pair<int, int> > > > myq;
 myq manage;
 
@@ -116,5 +112,5 @@
   {
     dp[node][prev] = val;
-    manage.push(make_pair(val, node*MAX+prev));
+    manage.push(make_pair(val, make_pair(node, prev)));
   }
 }
@@ -136,8 +132,8 @@
       graph[b].push_back(a);
     }
-    if (start == finish) { printf("0.0000\n"); continue; }
+    if (start == finish) { printf("0\n"); continue; }
     
     REP(i, points.size()) REP(j, points.size())
-      dp[i][j] = (i==start?0.0:1e12);
+      dp[i][j] = (i==start?0.0:FINF);
     
     manage = myq();
@@ -146,14 +142,14 @@
     {
       int j = graph[start][i];
-      update(j, i, get_dist(i,j)/S);
+      update(j, start, get_dist(start,j)/S);
     }
     
     // go from other vertices
-    double res = 1e12;
+    double res = FINF;
     while (!manage.empty())
     {
-      pair<double, int> temp = manage.top();
+      pair<double, pair<int, int> > temp = manage.top();
       manage.pop();
-      int node = temp.second/MAX, prev = temp.second%MAX;
+      int node = temp.second.first, prev = temp.second.second;
       double d = temp.first;
       if (dp[node][prev] < d) continue;
@@ -171,5 +167,5 @@
       }
     }
-    printf("%.4lf\n", res);
+    printf("%.9lf\n", res);
   }