B. The Meeting Place Cannot Be Changed

Codeforces

IDCF780B

Time5000ms

Memory256MB

Difficulty—

binary search

English · Original

Chinese · Translation

Formal · Original

The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction. At some points on the road there are _n_ friends, and _i_\-th of them is standing at the point _x__i_ meters and can move with any speed no greater than _v__i_ meters per second in any of the two directions along the road: south or north. You are to compute the minimum time needed to gather all the _n_ friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate. ## Input The first line contains single integer _n_ (2 ≤ _n_ ≤ 60 000) — the number of friends. The second line contains _n_ integers _x_1, _x_2, ..., _x__n_ (1 ≤ _x__i_ ≤ 109) — the current coordinates of the friends, in meters. The third line contains _n_ integers _v_1, _v_2, ..., _v__n_ (1 ≤ _v__i_ ≤ 109) — the maximum speeds of the friends, in meters per second. ## Output Print the minimum time (in seconds) needed for all the _n_ friends to meet at some point on the road. Your answer will be considered correct, if its absolute or relative error isn't greater than 10 - 6. Formally, let your answer be _a_, while jury's answer be _b_. Your answer will be considered correct if holds. [samples] ## Note In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

Bytecity的主干道是一条从南到北的直线。为方便起见，坐标以从最南端建筑物向北方向测量的米为单位。在道路的某些点上有 #cf_span[n] 位朋友，第 #cf_span[i] 位朋友位于 #cf_span[xi] 米处，可以以不超过 #cf_span[vi] 米/秒的任意速度沿道路向南或向北移动。你需要计算让所有 #cf_span[n] 位朋友在道路某一点集合所需的最短时间。注意，他们集合的点不需要是整数坐标。第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 60 000]）——朋友的数量。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn]（#cf_span[1 ≤ xi ≤ 109]）——朋友的当前位置，单位为米。第三行包含 #cf_span[n] 个整数 #cf_span[v1, v2, ..., vn]（#cf_span[1 ≤ vi ≤ 109]）——朋友的最大速度，单位为米/秒。请输出所有 #cf_span[n] 位朋友在道路某一点集合所需的最短时间（单位：秒）。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。形式化地，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，若成立，则你的答案正确。在第一个样例中，所有朋友可以在 #cf_span[2] 秒内聚集在点 #cf_span[5]。为实现这一点，第一位朋友应始终以最大速度向南移动，而第二位和第三位朋友应始终以最大速度向北移动。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 60 000]）——朋友的数量。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn]（#cf_span[1 ≤ xi ≤ 109]）——朋友的当前位置，单位为米。第三行包含 #cf_span[n] 个整数 #cf_span[v1, v2, ..., vn]（#cf_span[1 ≤ vi ≤ 109]）——朋友的最大速度，单位为米/秒。 ## Output 请输出所有 #cf_span[n] 位朋友在道路某一点集合所需的最短时间（单位：秒）。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。形式化地，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，若成立，则你的答案正确。 [samples] ## Note 在第一个样例中，所有朋友可以在 #cf_span[2] 秒内聚集在点 #cf_span[5]。为实现这一点，第一位朋友应始终以最大速度向南移动，而第二位和第三位朋友应始终以最大速度向北移动。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of friends. Let $ X = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n $ be the initial positions of the friends. Let $ V = (v_1, v_2, \dots, v_n) \in \mathbb{R}^n $ be the maximum speeds of the friends. **Constraints** 1. $ 2 \leq n \leq 60{,}000 $ 2. $ 1 \leq x_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq v_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum time $ t^* \in \mathbb{R}_{\geq 0} $ such that there exists a meeting point $ p \in \mathbb{R} $ satisfying: $$ \forall i \in \{1, \dots, n\}, \quad |x_i - p| \leq v_i \cdot t^* $$

Samples

Input #1

3
7 1 3
1 2 1

Output #1

2.000000000000

Input #2

4
5 10 3 2
2 3 2 4

Output #2

1.400000000000

API Response (JSON)

{
  "problem": {
    "name": "B. The Meeting Place Cannot Be Changed",
    "description": {
      "content": "The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction. At some points on the road ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF780B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.\n\nAt some points on the road ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Bytecity的主干道是一条从南到北的直线。为方便起见，坐标以从最南端建筑物向北方向测量的米为单位。\n\n在道路的某些点上有 #cf_span[n] 位朋友，第 #cf_span[i] 位朋友位于 #cf_span[xi] 米处，可以以不超过 #cf_span[vi] 米/秒的任意速度沿道路向南或向北移动。\n\n你需要计算让所有 #cf_span[n] 位朋友在道路某一点集合所需的最短时间。注意，他...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of friends.  \nLet $ X = (x_1, x_2, \\dots, x_n) \\in \\mathbb{R}^n $ be the initial positions of the friends.  \nLet $ V = (v_1, v_2, \\dots, v_n) \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments