Source code for submission s1010

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.  
  19. using namespace std;
  20. #define DEBUG(x) cerr << ">>> " << #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. #define MAXN 1100
  31. #define MAXC 2200
  32. #define MAXD 10100
  33.  
  34. int N;
  35. double S, T;
  36.  
  37. map<ll, int> n2i_map;
  38. ll i2n_map[MAXC];
  39. int iCnt;
  40. vector<int> way[MAXC];
  41. bool visited[MAXC][MAXC];
  42. double totDist[MAXC][MAXC];
  43. typedef priority_queue<pair<double, pair<int, int> > > qType;
  44. qType toVisit;
  45.  
  46. void clear_all() {
  47.   n2i_map.clear();
  48.   iCnt = 0;
  49.   REP(i,MAXC) way[i].clear();
  50.   REP(i,MAXC) REP(j, MAXC) visited[i][j] = false;
  51.   REP(i,MAXC) REP(j, MAXC) totDist[i][j] = 1.0 / 0.0;
  52.   toVisit = qType();
  53. }
  54.  
  55. int p2i(int x, int y, int z) {
  56.   ll p = x;
  57.   p *= MAXD;
  58.   p += y;
  59.   p *= MAXD;
  60.   p += z;
  61.   map<ll, int>::iterator iter = n2i_map.find(p);
  62.   if (iter != n2i_map.end()) return iter->second;
  63.   n2i_map[p] = iCnt;
  64.   i2n_map[iCnt] = p;
  65.   return iCnt++;
  66. }
  67.  
  68. ll i2n(int i) {
  69.   return i2n_map[i];
  70. }
  71.  
  72. int n2x(ll n) { return (n / MAXD) / MAXD; }
  73. int n2y(ll n) { return (n / MAXD) % MAXD; }
  74. int n2z(ll n) { return n % MAXD; }
  75.  
  76. double dist(int i1, int i2) {
  77.   ll n1 = i2n(i1), n2 = i2n(i2);
  78.   double x1 = n2x(n1), y1 = n2y(n1), z1 = n2z(n1);
  79.   double x2 = n2x(n2), y2 = n2y(n2), z2 = n2z(n2);
  80.   double dx = x1-x2, dy = y1-y2, dz = z1-z2;
  81.   return sqrt(dx*dx+dy*dy+dz*dz);
  82. }
  83.  
  84. double distT(int i1, int i2) {
  85.   return dist(i1, i2) / S;
  86. }
  87.  
  88. double ang(int i1, int d1, int i2, int d2) {
  89.   ll n1i = i2n(i1), n2i = i2n(i2);
  90.   ll n1d = i2n(d1), n2d = i2n(d2);
  91.   double x1i = n2x(n1i), y1i = n2y(n1i), z1i = n2z(n1i);
  92.   double x2i = n2x(n2i), y2i = n2y(n2i), z2i = n2z(n2i);
  93.   double x1d = n2x(n1d), y1d = n2y(n1d), z1d = n2z(n1d);
  94.   double x2d = n2x(n2d), y2d = n2y(n2d), z2d = n2z(n2d);
  95.   double dx1 = x1d-x1i, dy1 = y1d-y1i, dz1 = z1d-z1i;
  96.   double dx2 = x2d-x2i, dy2 = y2d-y2i, dz2 = z2d-z2i;
  97.   double num = dx1*dx2 + dy1*dy2 + dz1*dz2;
  98.   double den = dist(i1, d1) * dist(i2, d2);
  99.   return acos(num / den) * 180.0 / M_PI;
  100. }
  101.  
  102. double angT(int i1, int d1, int i2, int d2) {
  103.   return ang(i1, d1, i2, d2) / T;
  104. }
  105.  
  106. int main() {
  107.   while (scanf("%d%lf%lf", &N, &S, &T) == 3) {
  108.     clear_all();
  109.     int Si, Fi;
  110.     {
  111.       int x, y, z;
  112.       scanf("%d%d%d", &x, &y, &z);
  113.       Si = p2i(x, y, z);
  114.       scanf("%d%d%d", &x, &y, &z);
  115.       Fi = p2i(x, y, z);
  116.     }
  117.     REP(i,N) {
  118.       int x, y, z;
  119.       scanf("%d%d%d", &x, &y, &z);
  120.       int i1 = p2i(x, y, z);
  121.       scanf("%d%d%d", &x, &y, &z);
  122.       int i2 = p2i(x, y, z);
  123.       way[i1].push_back(i2);
  124.       way[i2].push_back(i1);
  125.     }
  126.     for (unsigned int jj = 0; jj < way[Si].size(); ++jj) {
  127.       int toD = way[Si][jj];
  128.       totDist[Si][toD] = 0;
  129.       toVisit.push(make_pair(0, make_pair(Si, toD)));
  130.     }
  131.     while (!toVisit.empty()) {
  132.       //printf("dist %lf\n", -toVisit.top().first);
  133.       pair<int, int> pr = toVisit.top().second;
  134.       toVisit.pop();
  135.       int at = pr.first, d = pr.second;
  136.       if (at == Fi) break;
  137.       if (visited[at][d]) continue;
  138.       //printf("vis %d %d\n", at, d);
  139.       visited[at][d] = true;
  140.       double dT = distT(at, d);
  141.       if (d == Fi) {
  142.         if (totDist[at][d]+dT < totDist[d][0]) {
  143.           totDist[d][0] = totDist[at][d]+dT;
  144.           toVisit.push(make_pair(-totDist[d][0], make_pair(d, 0)));
  145.         }
  146.         continue;
  147.       }
  148.       for (unsigned int jj = 0; jj < way[d].size(); ++jj) {
  149.         int toD = way[d][jj];
  150.         if (visited[d][toD]) continue;
  151.         //printf("  try %d %d\n", d, toD);
  152.         double aT = angT(at, d, d, toD);
  153.         if (totDist[at][d]+dT+aT < totDist[d][toD]) {
  154.           //printf("    go %d %d\n", d, toD);
  155.           totDist[d][toD] = totDist[at][d]+dT+aT;
  156.           toVisit.push(make_pair(-totDist[d][toD], make_pair(d, toD)));
  157.         }
  158.       }
  159.     }
  160.     printf("%lf\n", totDist[Fi][0]);
  161.   }
  162.   return 0;
  163. }
  164.  

Diff to submission s906

cockchaf.cpp

--- c4.s906.cteam002.cockchaf.cpp.0.cockchaf.cpp
+++ c4.s1010.cteam002.cockchaf.cpp.0.cockchaf.cpp
@@ -41,5 +41,5 @@
 bool visited[MAXC][MAXC];
 double totDist[MAXC][MAXC];
-typedef priority_queue<pair<int, pair<int, int> > > qType;
+typedef priority_queue<pair<double, pair<int, int> > > qType;
 qType toVisit;
 
@@ -130,4 +130,5 @@
     }
     while (!toVisit.empty()) {
+      //printf("dist %lf\n", -toVisit.top().first);
       pair<int, int> pr = toVisit.top().second;
       toVisit.pop();
@@ -135,4 +136,5 @@
       if (at == Fi) break;
       if (visited[at][d]) continue;
+      //printf("vis %d %d\n", at, d);
       visited[at][d] = true;
       double dT = distT(at, d);
@@ -147,6 +149,8 @@
         int toD = way[d][jj];
         if (visited[d][toD]) continue;
-        double aT = (d==Fi) ? 0 : angT(at, d, d, toD);
+        //printf("  try %d %d\n", d, toD);
+        double aT = angT(at, d, d, toD);
         if (totDist[at][d]+dT+aT < totDist[d][toD]) {
+          //printf("    go %d %d\n", d, toD);
           totDist[d][toD] = totDist[at][d]+dT+aT;
           toVisit.push(make_pair(-totDist[d][toD], make_pair(d, toD)));