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) cout << ">>> " << #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;
///////////////////////////////////////////////////////////////////////////
 
const int MAX = 2007;
int N, S, T;
double PI;
 
struct Point
{
  double x, y, z;
  Point() {}
  Point(double _x, double _y, double _z):
    x(_x), y(_y), z(_z) {}
 
  Point operator-(const Point & p) const
  {
    return Point(x-p.x, y-p.y, z-p.z);
  }
 
  bool operator==(const Point & p) const
  {
    return EQ(x, p.x) && EQ(y, p.y) && EQ(z, p.z);
  }
 
  double sz() const
  {
    return sqrt(x*x+y*y+z*z);
  }
 
  void read()
  {
    scanf("%lf%lf%lf", &x, &y, &z);
  }
};
 
double dot(const Point & p1, const Point & p2)
{
  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;
  double angle = acos(dot(v1, v2) / v1.sz() / v2.sz());
  return angle/PI*180.0;
}
 
vector<Point> points;
vector<int> graph[MAX];
int get_index(const Point & p)
{
  REP(i, points.size())
    if (p == points[i])
      return i;
  int index = points.size();
  graph[index].clear();
  points.push_back(p);
  return index;
}
 
double get_dist(int i, int j)
{
  return (points[i]-points[j]).sz();
}
 
double get_angle(int i, int j, int k)
{
  return angle(points[i], points[j], points[k]);
}
 
int new_point()
{
  Point p;
  p.read();
  return get_index(p);
}
 
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;
 
bool 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;
}
 
int main()
{
  PI = acos(-1.0);
 
  while (scanf("%d%d%d", &N, &S, &T) == 3)
  {
    ++step;
 
    points.clear();
    int start = new_point(), finish = new_point();
    REP(i, N)
    {
      int a = new_point(), b = new_point();
      graph[a].push_back(b);
      graph[b].push_back(a);
    }
    if (start == finish) { printf("0\n"); continue; }
 
    manage = myq();
    // go from start vertex
    REP(i, graph[start].size())
    {
      int j = graph[start][i];
      update(j, i, get_dist(i,j)/S);
    }
 
    // go from other vertices
    double res = 1e12;
    while (!manage.empty())
    {
      pair<double, int> temp = manage.top();
      manage.pop();
      int node = temp.second/MAX, prev = temp.second%MAX;
      double d = temp.first;
      if (dp[node][prev] < d) continue;
      if (node == finish)
      {
	res = d;
	break;
      }
 
      REP(i, graph[node].size())
      {
	int next = graph[node][i];
	double d2 = d + get_dist(node, next)/S + get_angle(prev, node, next)/T;
	update(next, node, d2);
      }
    }
    printf("%.4lf\n", res);
  }
 
  return 0;
}