A team of furry rescue rangers was sitting idle in their hollow tree when suddenly they received a signal of distress. In a few moments they were ready, and the dirigible of the rescue chipmunks hit the road.

We assume that the action takes place on a Cartesian plane. The headquarters of the rescuers is located at point (x_1, y_1), and the distress signal came from the point (x_2, y_2).

Due to Gadget's engineering talent, the rescuers' dirigible can instantly change its current velocity and direction of movement at any moment and as many times as needed. The only limitation is: the speed of the aircraft relative to the air can not exceed $v_{\operatorname{max}}$ meters per second.

Of course, Gadget is a true rescuer and wants to reach the destination as soon as possible. The matter is complicated by the fact that the wind is blowing in the air and it affects the movement of the dirigible. According to the weather forecast, the wind will be defined by the vector (v_{x}, v_{y}) for the nearest t seconds, and then will change to (w_{x}, w_{y}). These vectors give both the direction and velocity of the wind. Formally, if a dirigible is located at the point (x, y), while its own velocity relative to the air is equal to zero and the wind (u_{x}, u_{y}) is blowing, then after $T$ seconds the new position of the dirigible will be $(x + \tau \cdot u_{x}, y + \tau \cdot u_{y})$.

Gadget is busy piloting the aircraft, so she asked Chip to calculate how long will it take them to reach the destination if they fly optimally. He coped with the task easily, but Dale is convinced that Chip has given the random value, aiming only not to lose the face in front of Gadget. Dale has asked you to find the right answer.

It is guaranteed that the speed of the wind at any moment of time is strictly less than the maximum possible speed of the airship relative to the air.


-----Input-----

The first line of the input contains four integers x_1, y_1, x_2, y_2 (|x_1|,  |y_1|,  |x_2|,  |y_2| ≤ 10 000) — the coordinates of the rescuers' headquarters and the point, where signal of the distress came from, respectively. 

The second line contains two integers $v_{\operatorname{max}}$ and t (0 < v, t ≤ 1000), which are denoting the maximum speed of the chipmunk dirigible relative to the air and the moment of time when the wind changes according to the weather forecast, respectively. 

Next follow one per line two pairs of integer (v_{x}, v_{y}) and (w_{x}, w_{y}), describing the wind for the first t seconds and the wind that will blow at all the remaining time, respectively. It is guaranteed that $v_{x}^{2} + v_{y}^{2} < v_{\operatorname{max}}^{2}$ and $w_{x}^{2} + w_{y}^{2} < v_{\operatorname{max}}^{2}$.


-----Output-----

Print a single real value — the minimum time the rescuers need to get to point (x_2, y_2). You answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
0 0 5 5
3 2
-1 -1
-1 0

Output
3.729935587093555327

Input
0 0 0 1000
100 1000
-50 0
50 0

Output
11.547005383792516398

Source: codeforces | Difficulty: HARD
Tags: Geometry

Sorting

Mathematics


Solutions:
(x1, y1, x2, y2) = map(int, input().split())
(vmax, t) = map(int, input().split())
(vx, vy) = map(int, input().split())
(wx, wy) = map(int, input().split())
c1x = x1 + vx * t
c1y = y1 + vy * t
r1 = t * vmax
if (c1x - x2) ** 2 + (c1y - y2) ** 2 <= r1 ** 2:
	(t1l, t1r) = (0, t)
	itr = 0
	while t1r - t1l > 1e-10 and itr < 200:
		itr += 1
		t1 = (t1l + t1r) / 2
		cc1x = x1 + vx * t1
		cc1y = y1 + vy * t1
		rr1 = t1 * vmax
		if (cc1x - x2) ** 2 + (cc1y - y2) ** 2 <= rr1 ** 2:
			t1r = t1
		else:
			t1l = t1
	print(t1)
else:
	(t2l, t2r) = (0, 200000000)
	itr = 0
	while t2r - t2l > 1e-10 and itr < 200:
		itr += 1
		t2 = (t2l + t2r) / 2
		c2x = x2 - wx * t2
		c2y = y2 - wy * t2
		r2 = t2 * vmax
		if (c1x - c2x) ** 2 + (c1y - c2y) ** 2 <= (r1 + r2) ** 2:
			t2r = t2
		else:
			t2l = t2
	print(t + t2)


import math
(x1, y1, x2, y2) = list(map(int, input().split(' ')[:4]))
(u_max, tau) = list(map(int, input().split(' ')[:2]))
(vx, vy) = list(map(int, input().split(' ')[:2]))
(wx, wy) = list(map(int, input().split(' ')[:2]))
A = (x2 - x1, y2 - y1)
v = (-vx, -vy)
w = (-wx, -wy)
B = (A[0] + tau * v[0], A[1] + tau * v[1])

def solve_sqr_eq(a, b, c):
	d = b ** 2 - 4 * a * c
	if d >= 0:
		return ((-b + math.sqrt(d)) / (2 * a), (-b - math.sqrt(d)) / (2 * a))
	else:
		return None
a = v[0] ** 2 + v[1] ** 2 - u_max ** 2
b = 2 * A[0] * v[0] + 2 * A[1] * v[1]
c = A[0] ** 2 + A[1] ** 2
r = solve_sqr_eq(a, b, c)
if r is not None:
	(t1, t2) = r
	t_min = min(t1, t2)
	t_max = max(t1, t2)
	if 0 <= t_min <= tau:
		print(t_min)
		return
	if 0 <= t_max <= tau:
		print(t_max)
		return
a = w[0] ** 2 + w[1] ** 2 - u_max ** 2
b = 2 * B[0] * w[0] + 2 * B[1] * w[1] - u_max ** 2 * 2 * tau
c = B[0] ** 2 + B[1] ** 2 - u_max ** 2 * tau ** 2
r = solve_sqr_eq(a, b, c)
if r is not None:
	(t1, t2) = r
	t_min = min(t1, t2)
	t_max = max(t1, t2)
	if 0 <= t_min:
		print(t_min + tau)
		return
	if 0 <= t_max:
		print(t_max + tau)
		return


f = lambda : list(map(int, input().split()))
abs = lambda q: q[0] * q[0] + q[1] * q[1]
dot = lambda : v[0] * d[0] + v[1] * d[1]
get = lambda a, b, c: (b - (b * b - a * c) ** 0.5) / a
p = f()
d = [p[k + 2] - p[k] for k in [0, 1]]
(v, t) = f()
s = v * v
v = f()
i = get(abs(v) - s, dot(), abs(d))
d = [d[k] - t * v[k] for k in (0, 1)]
v = f()
j = get(abs(v) - s, dot() + t * s, abs(d) - t * t * s)
print(i if i < t else t + j)


scan = lambda : map(int, input().split())
(x1, y1, x2, y2) = scan()
(vmx, t) = scan()
(vx, vy) = scan()
(wx, wy) = scan()
(lb, ub, EPS) = (0, 1000000000000000.0, 1e-08)
while ub - lb > EPS:
	mid = (lb + ub) / 2
	(xx, yy) = (vx * mid, vy * mid) if t - mid > EPS else (vx * t + wx * (mid - t), vy * t + wy * (mid - t))
	if vmx * mid - ((x2 - x1 - xx) ** 2 + (y2 - y1 - yy) ** 2) ** 0.5 > EPS:
		ub = mid
	else:
		lb = mid
print('%.8f' % ub)


def f(T):
	t1 = min(t, T)
	t2 = max(T - t, 0)
	u = [v[0] * t1 + w[0] * t2, v[1] * t1 + w[1] * t2]
	C = [A[0] + u[0], A[1] + u[1]]
	dist = ((C[0] - B[0]) ** 2 + (C[1] - B[1]) ** 2) ** 0.5
	dist2 = Vmax * T
	return dist2 >= dist
read = lambda : map(int, input().split())
(A, B, v, w) = [[0, 0] for i in range(4)]
(A[0], A[1], B[0], B[1]) = read()
(Vmax, t) = read()
(v[0], v[1]) = read()
(w[0], w[1]) = read()
(L, R) = (0, 1000000000000.0)
for i in range(100):
	M = (L + R) / 2
	if f(M):
		R = M
	else:
		L = M
ans = R
print(ans)


(x1, y1, x2, y2) = map(float, input().split())
(vMax, t) = map(float, input().split())
(vx, vy) = map(float, input().split())
(wx, wy) = map(float, input().split())

def is_pos2(t1, t2):
	x1_n = x1 + vx * t1
	y1_n = y1 + vy * t1
	x2_n = x2 - wx * t2
	y2_n = y2 - wy * t2
	return (x1_n - x2_n) ** 2 + (y1_n - y2_n) ** 2 <= (vMax * (t1 + t2)) ** 2

def is_pos(tSum):
	t1 = min(t, tSum)
	t2 = max(0, tSum - t)
	return is_pos2(t1, t2)
if x1 == x2 and y1 == y2:
	print(0)
else:
	minT = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 / (vMax * 3)
	vabs = (vx ** 2 + vy ** 2) ** 0.5
	wabs = (wx ** 2 + wy ** 2) ** 0.5
	maxT = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 / (vMax - max(vabs, wabs))
	while (maxT - minT) / maxT > 10 ** (-7):
		medT = (maxT + minT) / 2
		if is_pos(medT):
			maxT = medT
		else:
			minT = medT
	print((minT + maxT) / 2)


(x, y, a, b) = map(int, input().split())
a -= x
b -= y
(v, t) = map(int, input().split())
(vx, vy) = map(int, input().split())
(ux, uy) = map(int, input().split())

def ok(T):
	U = max(0, T - t)
	V = min(t, T)
	X = a - U * ux - V * vx
	Y = b - U * uy - V * vy
	return X * X + Y * Y <= ((U + V) * v) ** 2
l = 0
r = 1000000000.0
while r - l > 1e-06:
	m = (l + r) / 2
	if ok(m):
		r = m
	else:
		l = m
print(r)


from math import sqrt
import re

class point2:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def length(self):
		return sqrt(self.x * self.x + self.y * self.y)

def xmult(a, b):
	return a.x * b.y - a.y * b.x

def dmult(a, b):
	return a.x * b.x + a.y * b.y
(x1, y1, x2, y2) = map(float, re.split('\\ +', input().strip()))
(v, t) = map(float, re.split('\\ +', input().strip()))
(vx, vy) = map(float, re.split('\\ +', input().strip()))
(wx, wy) = map(float, re.split('\\ +', input().strip()))
if x1 == x2 and y1 == y2:
	print(0)
	exit()
u = point2(vx, vy)
w = point2(wx, wy)
d = point2(x2 - x1, y2 - y1)
l = d.length()
h = xmult(d, u) / d.length()
s = dmult(d, u) / d.length()
v1 = sqrt(v * v - h * h) + s
t1 = d.length() / v1
if t1 <= t:
	print(t1)
else:
	x1 = x1 + t * u.x
	y1 = y1 + t * u.y
	(l, r) = (0.0, 1000000000.0)
	while r - l > 1e-07:
		mid = (l + r) / 2
		(_x1, _y1) = (x1 + mid * w.x, y1 + mid * w.y)
		d = point2(x2 - _x1, y2 - _y1).length()
		if d < (mid + t) * v:
			r = mid
		else:
			l = mid
	print(l + t)


f = lambda : map(int, input().split())
(a, b, c, d) = f()
(s, t) = f()
(vx, vy) = f()
(ux, uy) = f()

def g(m):
	vt = min(t, m)
	ut = max(0, m - t)
	x = c - a - ut * ux - vt * vx
	y = d - b - ut * uy - vt * vy
	return x * x + y * y > (m * s) ** 2
(l, r) = (0, 1000000000.0)
while r - l > 1e-06:
	m = (l + r) / 2
	if g(m):
		l = m
	else:
		r = m
print(r)


import sys
import math
read = lambda : list(map(int, sys.stdin.readline().split()))
(x1, y1, x2, y2) = read()
(vmax, t1) = read()
(vx, vy) = read()
(wx, wy) = read()
(x2, y2) = ((x2 - x1) / vmax, (y2 - y1) / vmax)
(vx, vy, wx, wy) = (vx / vmax, vy / vmax, wx / vmax, wy / vmax)
(lo, up) = (0, 10 ** 9)
for _ in range(100):
	t = (lo + up) / 2
	x = x2 - min(t, t1) * vx - max(t - t1, 0) * wx
	y = y2 - min(t, t1) * vy - max(t - t1, 0) * wy
	if x ** 2 + y ** 2 <= t ** 2:
		up = t
	else:
		lo = t
print(up)


d = list(map(int, input().split()))
(V, T) = map(int, input().split())
v = tuple(map(int, input().split()))
w = tuple(map(int, input().split()))
o = d[0:2]
d = d[2:4]
(l, r) = (0, 1000000000)
for i in range(300):
	(m, e) = ((l + r) / 2, o[:])
	if m <= T:
		e[0] += m * v[0]
		e[1] += m * v[1]
	else:
		e[0] += T * v[0]
		e[1] += T * v[1]
		e[0] += (m - T) * w[0]
		e[1] += (m - T) * w[1]
	if (d[0] - e[0]) * (d[0] - e[0]) + (d[1] - e[1]) * (d[1] - e[1]) <= V * V * m * m:
		a = m
		r = m - 1e-06
	else:
		l = m + 1e-06
print(a)


import math
(x1, y1, x2, y2) = map(float, input().split()[:4])
(v_max, t) = map(float, input().split()[:2])
(vx, vy) = map(float, input().split()[:2])
(wx, wy) = map(float, input().split()[:2])

def f(x1, y1, x2, y2, v_max, vx, vy):
	low = 0
	high = math.hypot(x2 - x1, y2 - y1) / (v_max - math.hypot(vx, vy))
	while high - low > 10 ** (-8):
		middle = (low + high) / 2.0
		x = x2 + vx * middle
		y = y2 + vy * middle
		t = math.hypot(x - x1, y - y1) / v_max
		if t > middle:
			low = middle
		else:
			high = middle
	return (low + high) / 2.0
time = f(x1, y1, x2, y2, v_max, -vx, -vy)
if time > t:
	time = f(x1, y1, x2 - vx * t + wx * t, y2 - vy * t + wy * t, v_max, -wx, -wy)
print(time)


import os, sys
from io import BytesIO, IOBase

def give_me_fuckin_answers_bitch(x1, y1, x2, y2, vmax, a1x, a1y, a2x, a2y, mid, t):
	(dx, dy) = (x2 - x1, y2 - y1)
	if mid < t:
		z = (dy - a1y * mid) ** 2 + (dx - a1x * mid) ** 2
	else:
		t1 = mid - t
		z = (dy - a1y * t - a2y * t1) ** 2 + (dx - a1x * t - a2x * t1) ** 2
	if z <= vmax * vmax * mid * mid:
		return 1
	return 0

def main():
	(x1, y1, x2, y2) = map(int, input().split())
	(vmax, t) = map(int, input().split())
	(a1x, a1y) = map(int, input().split())
	(a2x, a2y) = map(int, input().split())
	(hi, lo, ans) = (10 ** 9, 0, 10 ** 9)
	for _ in range(100000):
		mid = (hi + lo) / 2
		if give_me_fuckin_answers_bitch(x1, y1, x2, y2, vmax, a1x, a1y, a2x, a2y, mid, t):
			hi = mid
			ans = mid
		else:
			lo = mid
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from math import *

def direct(d, vmax, wx, wy):
	return d / (sqrt(vmax * vmax - wy * wy) + wx)

def fly(d, vmax, t, vx, vy, wx, wy, delta):
	sx = t * (vmax * cos(delta) + vx)
	sy = t * (vmax * sin(delta) + vy)
	(sx, sy, tx, ty) = (0, 0, d - sx, 0 - sy)
	alpha = angle_to(sx, sy, tx, ty)
	(tx, ty) = rotate_point(tx, ty, -alpha)
	(wx, wy) = rotate_point(wx, wy, -alpha)
	d = tx
	result = t + direct(d, vmax, wx, wy)
	return result

def rotate_point(x, y, alpha):
	newx = x * cos(alpha) - y * sin(alpha)
	newy = x * sin(alpha) + y * cos(alpha)
	return (newx, newy)

def angle_to(sx, sy, tx, ty):
	dx = tx - sx
	dy = ty - sy
	return atan2(dy, dx)

def angle_minus(alpha, v):
	alpha -= v
	if alpha < 0:
		alpha += 2 * pi
	return alpha

def angle_plus(alpha, v):
	alpha += v
	if alpha > 2 * pi:
		alpha -= 2 * pi
	return alpha

def angle_diff(alpha, beta):
	result = alpha - beta
	if result < 0:
		result += 2 * pi
	elif result > 2 * pi:
		result -= 2 * pi
	return result

def main():
	(sx, sy, tx, ty) = map(float, input().split())
	(vmax, t) = map(float, input().split())
	(vx, vy) = map(float, input().split())
	(wx, wy) = map(float, input().split())
	(sx, sy, tx, ty) = (0, 0, tx - sx, ty - sy)
	alpha = angle_to(sx, sy, tx, ty)
	(tx, ty) = rotate_point(tx, ty, -alpha)
	(vx, vy) = rotate_point(vx, vy, -alpha)
	(wx, wy) = rotate_point(wx, wy, -alpha)
	d = tx
	tau1 = direct(d, vmax, vx, vy)
	if tau1 <= t:
		print(tau1)
		return
	alpha = 0
	while True:
		lower = angle_minus(alpha, 0.1)
		upper = angle_plus(alpha, 0.1)
		ta = fly(d, vmax, t, vx, vy, wx, wy, alpha)
		tl = fly(d, vmax, t, vx, vy, wx, wy, lower)
		tu = fly(d, vmax, t, vx, vy, wx, wy, upper)
		if tl > ta and tu > ta:
			break
		else:
			alpha = angle_plus(alpha, 0.1)
	for i in range(100):
		delta = angle_diff(upper, lower)
		new_low = fly(d, vmax, t, vx, vy, wx, wy, angle_plus(lower, delta / 3))
		new_high = fly(d, vmax, t, vx, vy, wx, wy, angle_plus(lower, 2 * delta / 3))
		if new_low < new_high:
			upper = angle_plus(lower, 2 * delta / 3)
		else:
			lower = angle_plus(lower, delta / 3)
	print(fly(d, vmax, t, vx, vy, wx, wy, upper))
main()