Skip to content

Instantly share code, notes, and snippets.

@not522
Created June 30, 2013 17:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save not522/5895999 to your computer and use it in GitHub Desktop.
Save not522/5895999 to your computer and use it in GitHub Desktop.
#include<iostream>
#include<cstdio>
#include<complex>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define X real()
#define Y imag()
typedef double D;
typedef complex<D> P;
const D EPS = 1e-8;
const D PI = acos(-1);
int sig(D a, D b = 0) {return a < b - EPS ? -1 : a > b + EPS ? 1 : 0;}
D sr(D a) {return sqrt(max(a, (D)0));}
D det(P a, P b) {return a.X * b.Y - a.Y * b.X;}
P s, g, w;
D v, wr, wv, b, alpha;
int n;
// 2次方程式を解く
pair<D, D> solve2D(D a, D b, D c) {return make_pair((-b + sr(b * b - 4 * a * c)) / (2 * a), (-b - sr(b * b - 4 * a * c)) / (2 * a));}
// 直線で到達できるかチェック
bool check(P a, P b) {
D dx = polar(v, arg(b - a)).X, dy = polar(v, arg(b - a)).Y;
if (sig(pow(a.X * dx + a.Y * dy - wr * wv, 2) - (v * v - wv * wv) * (norm(a) - wr * wr)) <= 0) return true;
pair<D, D> pp = solve2D(v * v - wv * wv, 2 * (a.X * dx + a.Y * dy - wr * wv), norm(a) - wr * wr);
D tt = abs(b - a) / v;
if (0 < sig(pp.first) && sig(pp.first, tt) < 0) return false;
if (0 < sig(pp.second) && sig(pp.second, tt) < 0) return false;
return true;
}
D solve(P p) {
D r = abs(p), theta = arg(p);
// r=exp(b*(theta*C))のC(積分定数)を求める
D c = log(r) / b - theta;
// 下限を入るところの角度、上限を原点とゴールを結んだ角度で二分探索
D low = arg(p), high = arg(g);
if (sig(high, theta) < 0) high += 2 * PI;
// ゴールの角度まで螺旋上を回っていった時に、ゴールが呪われていたらだめ
if (sig(abs(exp((high + c) * b)), abs(g)) > 0) return 1e100;
// 原点からの半直線と螺旋のなす角が一定であることを利用して二分探索
rep (iii, 1000) {
D mid = (low + high) / 2;
P mp = polar(exp((mid + c) * b), mid);
P dir = mp * polar((D)1, alpha);
if (det(dir, g - mp) >= 0) low = mid;
else high = mid;
}
P rp = polar(exp((low + c) * b), low);
return (abs(rp) - wr) / wv + abs(rp - g) / v;
}
int main() {
cin >> s.X >> s.Y >> g.X >> g.Y >> v >> n >> w.X >> w.Y >> wr >> wv;
// 魔女を原点とする
s -= w;
g -= w;
if (check(s, g)) {
// 直線で行ける場合
printf("%.100lf\n", abs(s - g) / v);
} else {
// 呪いの外周を回る時の軌道がr=exp(b*(theta+C))
b = wv / sr(v * v - wv * wv);
// 原点からの半直線と螺旋のなす角
alpha = acos(b / sr(b * b + 1));
D res = 1e100;
// 扱いやすいようにスタートをx軸のx<0の方になるように回す
g *= polar((D)1, PI - arg(s));
s = -abs(s);
// ゴールはy<0にしておく
if (g.Y > 0) g.Y = -g.Y;
// 螺旋に接する直線の角度で入る
pair<D, D> xx = solve2D(s.X * s.X, -2 * s.X * wr * wv, wv * wv * s.X * s.X - v * v * s.X * s.X + v * v * wr * wr);
pair<D, D> tt;
tt.first = solve2D(v * v - wv * wv, 2 * (s.X * xx.first - wr * wv), s.X * s.X - wr * wr).first;
tt.second = solve2D(v * v - wv * wv, 2 * (s.X * xx.second - wr * wv), s.X * s.X - wr * wr).first;
if (sig(tt.first) > 0) res = min(res, solve(s + tt.first * P(xx.first, -sr(v * v - xx.first * xx.first))));
if (sig(tt.second) > 0) res = min(res, solve(s + tt.second * P(xx.second, -sr(v * v - xx.second * xx.second))));
if (res < 1e90) printf("%.100lf\n", res);
else puts("Impossible");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment