Created
June 30, 2013 17:10
-
-
Save not522/5895999 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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