Long time no see! Let's get straight to today's topic...
E - Closest Moment
Problem. Takahashi and Aoki walk on a two-dimensional plane.
Takahashi starts at point $TS=(TS_X, TS_Y)$ and walks straight to point $TG=(TG_X, TG_Y)$. Likewise, Aoki starts at point $AS=(AS_X, AS_Y)$ and walks straight to point $AG=(AG_X, AG_Y)$.
Takahashi and Aoki depart simultaneously and walk at the speed of $1$ unit per second, and they immediately stop moving once they reach their respective goals. Note that Takahashi and Aoki do not necessarily stop at the same time.
Find the minimum distance between Takahashi and Aoki, including the moments they start walking and after either of them has reached their goal.
Vector equations of a line
We will view $TS, TG, AS, AG$ as two-dimensional vectors. Let $t_T=|TG-TS|$ and $t_A=|AG-AS|$ be the total time Takahashi and Aoki spend walking, respectively. Since both people walk in a straight line, we can determine their location at any given time by the vector equations
- $T(t)=TS+\dfrac{t}{t_T}(TG-TS)$ for $t\in[0, t_T]$
- $A(t)=AS+\dfrac{t}{t_A}(AG-AS)$ for $t\in[0, t_A]$
for Takahashi and Aoki, respectively. Here, $\dfrac{1}{t_T}(TG - TS)$ is the velocity vector in the direction of Takahashi’s movement (with speed $1$), and similarly for Aoki.
Divide into two stages
As the problem suggests, Takahashi and Aoki do not necessarily stop at the same time. Without loss of generality, suppose $t_T\leq t_A$. We can divide the problem into two stages:
- For $t\in[0, t_T]$, both Takahashi and Aoki are walking towards their goals.
- For $t\in[t_T, t_A]$, only Aoki is walking towards his goal.
We will find the minimum distances for both stages and take the smaller of the two as the final answer.
Rephrase the question
Let's think about what happens when only Aoki is moving for $t\in[t_T, t_A]$. During this stage, Takahashi stays at $T(t_T)=TG$ while Aoki moves from $A(t_T)$ to $A(t_A)=AG$. From Takahashi’s perspective (fixed at $TG$ during this stage), Aoki’s position is $A(t)-TG=(AS-TG)+\dfrac{t}{t_A}(AG-AS)$, which describes a line segment for $t\in[t_T, t_A]$.
We can apply the same idea to when both Takahashi and Aoki are moving. For $t\in[0, t_T]$, Aoki's position from Takahashi's perspective is $A(t)-T(t)=(AS-TS)+t\left(\dfrac1{t_A}(AG-AS)-\dfrac1{t_T}(TG-TS)\right)$, again tracing a line segment relative to Takahashi.
In both scenarios, when we look at the two's movements from Takahashi's perspective, we observe that Takahashi always stays at the origin while Aoki moves along some line segment. Thus, we can rephrase the problem as finding the minimum distance between the origin and a given line segment.
The minimum distance between the origin and a line segment
Given two points represented by vectors $\mathbf{a}=(x_a, y_a)$ and $\mathbf{b}=(x_b, y_b)$, our goal is to find the minimum distance between the origin and the line segment connecting the two points.
We can represent the line segment as a vector equation $L(s)=\mathbf{a}+s(\mathbf{b}-\mathbf{a})$, giving us a point on the line segment for $s\in[0, 1]$. (Verify that $L(0)=\mathbf{a}$ and $L(1)=\mathbf{b}$.)
The distance between the origin and a point $L(s)$ is
$$|L(s)|=\sqrt{(x_a+s(x_b-x_a))^2+(y_a+s(y_b-y_a))^2}.$$
To minimize $|L(s)|$, we can solve for $\dfrac{\text{d}}{\text{d}s}|L(s)|=0$, but the derivative is a bit complicated. We can instead utilize the fact that $|L(s)|$ is minimum whenever $|L(s)|^2$ is minimum, and use this to solve for $\dfrac{\text{d}}{\text{d}s}|L(s)|^2=0$ instead. Computing the derivative yields
$$\frac{\text{d}}{\text{d}s}|L(s)|^2=2(x_b-x_a)(x_a+s(x_b-x_a))+2(y_b-y_a)(y_a+s(y_b-y_a))=0.$$
After simplifying, we obtain
$$s=-\dfrac{x_a(x_b-x_a)+y_a(y_b-y_a)}{(x_b-x_a)^2+(y_b-y_a)^2}=-\dfrac{\mathbf{a}\cdot(\mathbf{b}-\mathbf{a})}{|\mathbf{b}-\mathbf{a}|^2}$$
that minimizes $|L(s)|$.
Be careful though: if $s\not\in[0, 1]$, $L(s)$ will not be on the line segment. In particular, if $s<0$, the closest point on the line segment becomes $L(0)=\mathbf{a}$, whereas $s>1$ results in the closest point at $L(1)=\mathbf{b}$.
Moreover, the above $s$ only exists if $|\mathbf{b}-\mathbf{a}|^2\neq0$; that is, if $\mathbf{a}\neq\mathbf{b}$. The implementation at the bottom of this page handles the case $\mathbf{a}=\mathbf{b}$ carefully by simply returning the distance from the origin to $\mathbf{a}$.
Alternative solution
The above method uses direct computation to obtain the minimum distance between the origin and a line segment in $\mathcal{O}(1)$ time. Since $|L(s)|$, the distance between the origin and a line, is a convex function, it is also possible to compute the minimum distance via ternary search in $\mathcal{O}(-\log\varepsilon)$ time for bounded error $\varepsilon>0$.
For more information on implementing ternary search for this problem, check out the official editorial here.
Full implementation in Python
from math import sqrt
def squared_norm(x, y):
return x * x + y * y
def dot(xa, ya, xb, yb):
return xa * xb + ya * yb
def min_dist_origin(xa, ya, xb, yb):
if xa == xb and ya == yb:
return sqrt(squared_norm(xa, ya))
s = -dot(xa, ya, xb - xa, yb - ya) / squared_norm(xb - xa, yb - ya)
if s < 0:
return sqrt(squared_norm(xa, ya))
if s > 1:
return sqrt(squared_norm(xb, yb))
return sqrt(squared_norm(xa + s * (xb - xa), ya + s * (yb - ya)))
def solve():
tsx, tsy, tgx, tgy = (float(x) for x in input().split())
asx, asy, agx, agy = (float(x) for x in input().split())
time_t = sqrt(squared_norm(tgx - tsx, tgy - tsy))
time_a = sqrt(squared_norm(agx - asx, agy - asy))
time_min = min(time_t, time_a)
tmx = tsx + (tgx - tsx) * time_min / time_t
tmy = tsy + (tgy - tsy) * time_min / time_t
amx = asx + (agx - asx) * time_min / time_a
amy = asy + (agy - asy) * time_min / time_a
result_start_mid = min_dist_origin(asx - tsx, asy - tsy, amx - tmx, amy - tmy)
result_mid_goal = min_dist_origin(amx - tmx, amy - tmy, agx - tgx, agy - tgy)
return min(result_start_mid, result_mid_goal)
for _ in range(int(input())):
print(f"{solve():.10f}")
Just like that...
...You solved ABC426E. Best wishes as always, and watch out for those terrible TLEs! ⏱️🚀