cockchaf.cpp

#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) cerr << ">>> " << #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;
//////////////////////////////////
 
#define MAXN 1100
#define MAXC 2200
#define MAXD 10100
 
int N;
double S, T;
 
map<ll, int> n2i_map;
ll i2n_map[MAXC];
int iCnt;
vector<int> way[MAXC];
bool visited[MAXC][MAXC];
double totDist[MAXC][MAXC];
typedef priority_queue<pair<int, pair<int, int> > > qType;
qType toVisit;
 
void clear_all() {
  n2i_map.clear();
  iCnt = 0;
  REP(i,MAXC) way[i].clear();
  REP(i,MAXC) REP(j, MAXC) visited[i][j] = false;
  REP(i,MAXC) REP(j, MAXC) totDist[i][j] = 1.0 / 0.0;
  toVisit = qType();
}
 
int p2i(int x, int y, int z) {
  ll p = x;
  p *= MAXD;
  p += y;
  p *= MAXD;
  p += z;
  map<ll, int>::iterator iter = n2i_map.find(p);
  if (iter != n2i_map.end()) return iter->second;
  n2i_map[p] = iCnt;
  i2n_map[iCnt] = p;
  return iCnt++;
}
 
ll i2n(int i) {
  return i2n_map[i];
}
 
int n2x(ll n) { return (n / MAXD) / MAXD; }
int n2y(ll n) { return (n / MAXD) % MAXD; }
int n2z(ll n) { return n % MAXD; }
 
double dist(int i1, int i2) {
  ll n1 = i2n(i1), n2 = i2n(i2);
  double x1 = n2x(n1), y1 = n2y(n1), z1 = n2z(n1);
  double x2 = n2x(n2), y2 = n2y(n2), z2 = n2z(n2);
  double dx = x1-x2, dy = y1-y2, dz = z1-z2;
  return sqrt(dx*dx+dy*dy+dz*dz);
}
 
double distT(int i1, int i2) {
  return dist(i1, i2) / S;
}
 
double ang(int i1, int d1, int i2, int d2) {
  ll n1i = i2n(i1), n2i = i2n(i2);
  ll n1d = i2n(d1), n2d = i2n(d2);
  double x1i = n2x(n1i), y1i = n2y(n1i), z1i = n2z(n1i);
  double x2i = n2x(n2i), y2i = n2y(n2i), z2i = n2z(n2i);
  double x1d = n2x(n1d), y1d = n2y(n1d), z1d = n2z(n1d);
  double x2d = n2x(n2d), y2d = n2y(n2d), z2d = n2z(n2d);
  double dx1 = x1d-x1i, dy1 = y1d-y1i, dz1 = z1d-z1i;
  double dx2 = x2d-x2i, dy2 = y2d-y2i, dz2 = z2d-z2i;
  double num = dx1*dx2 + dy1*dy2 + dz1*dz2;
  double den = dist(i1, d1) * dist(i2, d2);
  return acos(num / den) * 180.0 / M_PI;
}
 
double angT(int i1, int d1, int i2, int d2) {
  return ang(i1, d1, i2, d2) / T;
}
 
int main() {
  while (scanf("%d%lf%lf", &N, &S, &T) == 3) {
    clear_all();
    int Si, Fi;
    {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      Si = p2i(x, y, z);
      scanf("%d%d%d", &x, &y, &z);
      Fi = p2i(x, y, z);
    }
    REP(i,N) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      int i1 = p2i(x, y, z);
      scanf("%d%d%d", &x, &y, &z);
      int i2 = p2i(x, y, z);
      way[i1].push_back(i2);
      way[i2].push_back(i1);
    }
    for (unsigned int jj = 0; jj < way[Si].size(); ++jj) {
      int toD = way[Si][jj];
      totDist[Si][toD] = 0;
      toVisit.push(make_pair(0, make_pair(Si, toD)));
    }
    while (!toVisit.empty()) {
      pair<int, int> pr = toVisit.top().second;
      toVisit.pop();
      int at = pr.first, d = pr.second;
      if (at == Fi) break;
      if (visited[at][d]) continue;
      visited[at][d] = true;
      double dT = distT(at, d);
      if (d == Fi) {
        if (totDist[at][d]+dT < totDist[d][0]) {
          totDist[d][0] = totDist[at][d]+dT;
          toVisit.push(make_pair(-totDist[d][0], make_pair(d, 0)));
        }
        continue;
      }
      for (unsigned int jj = 0; jj < way[d].size(); ++jj) {
        int toD = way[d][jj];
        if (visited[d][toD]) continue;
        double aT = (d==Fi) ? 0 : angT(at, d, d, toD);
        if (totDist[at][d]+dT+aT < totDist[d][toD]) {
          totDist[d][toD] = totDist[at][d]+dT+aT;
          toVisit.push(make_pair(-totDist[d][toD], make_pair(d, toD)));
        }
      }
    }
    printf("%lf\n", totDist[Fi][0]);
  }
  return 0;
}