F. Two Points

Codeforces

IDCF10097F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are two points (x1, y1) and (x2, y2) on the plane. They move with the velocities (vx1, vy1) and (vx2, vy2). Find the minimal distance between them ever in future. The first line contains four space-separated integers x1, y1, x2, y2 ( - 104 ≤ x1, y1, x2, y2 ≤ 104) — the coordinates of the points. The second line contains four space-separated integers vx1, vy1, vx2, vy2 ( - 104 ≤ vx1, vy1, vx2, vy2 ≤ 104) — the velocities of the points. Output a real number d — the minimal distance between the points. Absolute or relative error of the answer should be less than 10 - 6. ## Input The first line contains four space-separated integers x1, y1, x2, y2 ( - 104 ≤ x1, y1, x2, y2 ≤ 104) — the coordinates of the points.The second line contains four space-separated integers vx1, vy1, vx2, vy2 ( - 104 ≤ vx1, vy1, vx2, vy2 ≤ 104) — the velocities of the points. ## Output Output a real number d — the minimal distance between the points. Absolute or relative error of the answer should be less than 10 - 6. [samples]

**Definitions** Let $ \mathbf{p}_1 = (x_1, y_1), \mathbf{p}_2 = (x_2, y_2) \in \mathbb{R}^2 $ be initial positions. Let $ \mathbf{v}_1 = (v_{x1}, v_{y1}), \mathbf{v}_2 = (v_{x2}, v_{y2}) \in \mathbb{R}^2 $ be constant velocities. **Constraints** $ |x_1|, |y_1|, |x_2|, |y_2|, |v_{x1}|, |v_{y1}|, |v_{x2}|, |v_{y2}| \leq 10^4 $ **Objective** Define the relative position and velocity: $ \mathbf{r}(t) = (\mathbf{p}_2 + t\mathbf{v}_2) - (\mathbf{p}_1 + t\mathbf{v}_1) = \mathbf{r}_0 + t\mathbf{v}_r $, where $ \mathbf{r}_0 = (x_2 - x_1, y_2 - y_1) $, $ \mathbf{v}_r = (v_{x2} - v_{x1}, v_{y2} - v_{y1}) $. Find the minimal Euclidean distance: $$ d = \min_{t \geq 0} \|\mathbf{r}(t)\| = \min_{t \geq 0} \sqrt{ (\mathbf{r}_0 + t\mathbf{v}_r) \cdot (\mathbf{r}_0 + t\mathbf{v}_r) } $$

API Response (JSON)

{
  "problem": {
    "name": "F. Two Points",
    "description": {
      "content": "There are two points (x1, y1) and (x2, y2) on the plane. They move with the velocities (vx1, vy1) and (vx2, vy2). Find the minimal distance between them ever in future. The first line contains four s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are two points (x1, y1) and (x2, y2) on the plane. They move with the velocities (vx1, vy1) and (vx2, vy2). Find the minimal distance between them ever in future.\n\nThe first line contains four s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\mathbf{p}_1 = (x_1, y_1), \\mathbf{p}_2 = (x_2, y_2) \\in \\mathbb{R}^2 $ be initial positions.  \nLet $ \\mathbf{v}_1 = (v_{x1}, v_{y1}), \\mathbf{v}_2 = (v_{x2}, v_{y2}) \\in \\math...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments