A. Beru-taxi

Codeforces

IDCF706A

Time1000ms

Memory256MB

Difficulty—

brute forcegeometryimplementation

English · Original

Chinese · Translation

Formal · Original

Vasiliy lives at point (_a_, _b_) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested _n_ available Beru-taxi nearby. The _i_\-th taxi is located at point (_x__i_, _y__i_) and moves with a speed _v__i_. Consider that each of _n_ drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars. ## Input The first line of the input contains two integers _a_ and _b_ ( - 100 ≤ _a_, _b_ ≤ 100) — coordinates of Vasiliy's home. The second line contains a single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of available Beru-taxi cars nearby. The _i_\-th of the following _n_ lines contains three integers _x__i_, _y__i_ and _v__i_ ( - 100 ≤ _x__i_, _y__i_ ≤ 100, 1 ≤ _v__i_ ≤ 100) — the coordinates of the _i_\-th car and its speed. It's allowed that several cars are located at the same point. Also, cars may be located at exactly the same point where Vasiliy lives. ## Output Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. 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 . [samples] ## Note In the first sample, first taxi will get to Vasiliy in time 2, and second will do this in time 1, therefore 1 is the answer. In the second sample, cars 2 and 3 will arrive simultaneously.

Vasiliy 居住在坐标平面上的点 #cf_span[(a, b)]。他赶着去上班，因此希望尽快离开家。新应用提示附近有 #cf_span[n] 辆可用的 Beru 出租车。第 #cf_span[i] 辆出租车位于点 #cf_span[(xi, yi)]，并以速度 #cf_span[vi] 行驶。假设每辆出租车都会直接朝 Vasiliy 移动，并以最大可能速度行驶。请计算 Vasiliy 能乘坐上任何一辆 Beru 出租车的最短时间。输入的第一行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[ - 100 ≤ a, b ≤ 100]) —— Vasiliy 家的坐标。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 附近可用的 Beru 出租车数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含三个整数 #cf_span[xi]、#cf_span[yi] 和 #cf_span[vi] (#cf_span[ - 100 ≤ xi, yi ≤ 100], #cf_span[1 ≤ vi ≤ 100]) —— 第 #cf_span[i] 辆车的坐标及其速度。允许多辆车位于同一位置。此外，车辆也可能恰好位于 Vasiliy 居住的点上。请输出一个实数 —— Vasiliy 能乘坐上任何一辆 Beru 出租车所需的最短时间。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。具体而言：假设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确，当且仅当。在第一个样例中，第一辆出租车将在时间 #cf_span[2] 到达 Vasiliy，第二辆将在时间 #cf_span[1] 到达，因此答案为 #cf_span[1]。在第二个样例中，第 #cf_span[2] 辆和第 #cf_span[3] 辆出租车将同时到达。 ## Input 输入的第一行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[ - 100 ≤ a, b ≤ 100]) —— Vasiliy 家的坐标。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 附近可用的 Beru 出租车数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含三个整数 #cf_span[xi]、#cf_span[yi] 和 #cf_span[vi] (#cf_span[ - 100 ≤ xi, yi ≤ 100], #cf_span[1 ≤ vi ≤ 100]) —— 第 #cf_span[i] 辆车的坐标及其速度。允许多辆车位于同一位置。此外，车辆也可能恰好位于 Vasiliy 居住的点上。 ## Output 请输出一个实数 —— Vasiliy 能乘坐上任何一辆 Beru 出租车所需的最短时间。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。具体而言：假设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确，当且仅当。 [samples] ## Note 在第一个样例中，第一辆出租车将在时间 #cf_span[2] 到达 Vasiliy，第二辆将在时间 #cf_span[1] 到达，因此 #cf_span[1] 是答案。在第二个样例中，第 #cf_span[2] 辆和第 #cf_span[3] 辆出租车将同时到达。

**Definitions** Let $ (a, b) \in \mathbb{R}^2 $ be Vasiliy's position. Let $ n \in \mathbb{Z}^+ $ be the number of taxis. For each $ i \in \{1, \dots, n\} $, let $ (x_i, y_i) \in \mathbb{R}^2 $ be the position of taxi $ i $, and $ v_i \in \mathbb{R}^+ $ its speed. **Constraints** 1. $ -100 \leq a, b \leq 100 $ 2. $ 1 \leq n \leq 1000 $ 3. $ -100 \leq x_i, y_i \leq 100 $ 4. $ 1 \leq v_i \leq 100 $ **Objective** Compute the minimum time $ t_{\min} $ for any taxi to reach Vasiliy: $$ t_{\min} = \min_{1 \leq i \leq n} \left( \frac{\sqrt{(x_i - a)^2 + (y_i - b)^2}}{v_i} \right) $$

Samples

Input #1

Output #1

1.00000000000000000000

Input #2

Output #2

0.50000000000000000000

API Response (JSON)

{
  "problem": {
    "name": "A. Beru-taxi",
    "description": {
      "content": "Vasiliy lives at point (_a_, _b_) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested _n_ available Beru-taxi nearby. The _i_\\",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF706A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasiliy lives at point (_a_, _b_) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested _n_ available Beru-taxi nearby. The _i_\\...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasiliy 居住在坐标平面上的点 #cf_span[(a, b)]。他赶着去上班，因此希望尽快离开家。新应用提示附近有 #cf_span[n] 辆可用的 Beru 出租车。第 #cf_span[i] 辆出租车位于点 #cf_span[(xi, yi)]，并以速度 #cf_span[vi] 行驶。\n\n假设每辆出租车都会直接朝 Vasiliy 移动，并以最大可能速度行驶。请计算 Vasiliy 能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ (a, b) \\in \\mathbb{R}^2 $ be Vasiliy's position.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of taxis.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ (x_i, y_i) \\in \\mathbb{R}^2 $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments