F. Tourist

Codeforces

IDCF76F

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdp

English · Original

Chinese · Translation

Formal · Original

Tourist walks along the _X_ axis. He can choose either of two directions and any speed not exceeding _V_. He can also stand without moving anywhere. He knows from newspapers that at time _t_1 in the point with coordinate _x_1 an interesting event will occur, at time _t_2 in the point with coordinate _x_2 — another one, and so on up to (_x__n_, _t__n_). Interesting events are short so we can assume they are immediate. Event _i_ counts visited if at time _t__i_ tourist was at point with coordinate _x__i_. Write program tourist that will find maximum number of events tourist if: * at the beginning (when time is equal to 0) tourist appears at point 0, * tourist can choose initial point for himself. Yes, you should answer on two similar but different questions. ## Input The first line of input contains single integer number _N_ (1 ≤ _N_ ≤ 100000) — number of interesting events. The following _N_ lines contain two integers _x__i_ and _t__i_ — coordinate and time of the _i_\-th event. The last line of the input contains integer _V_ — maximum speed of the tourist. All _x__i_ will be within range - 2·108 ≤ _x__i_ ≤ 2·108, all _t__i_ will be between 1 and 2·106 inclusive. _V_ will be positive and will not exceed 1000. The input may contain events that happen at the same time or in the same place but not in the same place at the same time. ## Output The only line of the output should contain two space-sepatated integers — maximum number of events tourist can visit in he starts moving from point 0 at time 0, and maximum number of events tourist can visit if he chooses the initial point for himself. [samples]

旅游者沿着 #cf_span[X] 轴行走。他可以选择两个方向中的任意一个，以及不超过 #cf_span[V] 的任意速度。他也可以选择原地不动。他从报纸上得知，在时间 #cf_span[t1]、坐标为 #cf_span[x1] 的点将发生一个有趣事件，在时间 #cf_span[t2]、坐标为 #cf_span[x2] 的点将发生另一个事件，依此类推，直到 (#cf_span[xn, tn])。这些有趣事件持续时间极短，可视为瞬时发生。若在时间 #cf_span[ti] 旅游者位于坐标为 #cf_span[xi] 的点，则认为事件 #cf_span[i] 被访问过。请编写程序，计算旅游者最多能访问多少个事件，满足以下两个相似但不同的条件：是的，你需要回答两个相似但不同的问题。输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 100000]) —— 有趣事件的数量。接下来的 #cf_span[N] 行每行包含两个整数 #cf_span[xi] 和 #cf_span[ti] —— 第 #cf_span[i] 个事件的坐标和时间。输入的最后一行包含一个整数 #cf_span[V] —— 旅游者的最大速度。所有 #cf_span[xi] 均在范围 #cf_span[ - 2·108 ≤ xi ≤ 2·108] 内，所有 #cf_span[ti] 均在 #cf_span[1] 到 #cf_span[2·106] 之间（含端点）。#cf_span[V] 为正数且不超过 1000。输入可能包含在同一时间或同一地点发生的事件，但不会在同一时间同一地点发生事件。 ## Input 输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 100000]) —— 有趣事件的数量。接下来的 #cf_span[N] 行每行包含两个整数 #cf_span[xi] 和 #cf_span[ti] —— 第 #cf_span[i] 个事件的坐标和时间。输入的最后一行包含一个整数 #cf_span[V] —— 旅游者的最大速度。所有 #cf_span[xi] 均在范围 #cf_span[ - 2·108 ≤ xi ≤ 2·108] 内，所有 #cf_span[ti] 均在 #cf_span[1] 到 #cf_span[2·106] 之间（含端点）。#cf_span[V] 为正数且不超过 1000。输入可能包含在同一时间或同一地点发生的事件，但不会在同一时间同一地点发生事件。 ## Output 输出仅一行，包含两个用空格分隔的整数 —— 旅游者从时间 0 从坐标 0 出发时最多能访问的事件数，以及旅游者可以自行选择初始位置时最多能访问的事件数。 [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of events. For each $ i \in \{1, \dots, N\} $, let $ (x_i, t_i) \in \mathbb{R} \times \mathbb{Z}^+ $ denote the coordinate and time of the $ i $-th event. Let $ V \in \mathbb{R}^+ $ be the maximum speed of the tourist. Let $ p_0 = 0 $ be the initial position at time $ 0 $ for the first scenario. Let $ p_0' \in \mathbb{R} $ be the freely chosen initial position at time $ 0 $ for the second scenario. **Constraints** 1. $ 1 \leq N \leq 100000 $ 2. $ -2 \cdot 10^8 \leq x_i \leq 2 \cdot 10^8 $ for all $ i $ 3. $ 1 \leq t_i \leq 2 \cdot 10^6 $ for all $ i $ 4. $ 0 < V \leq 1000 $ 5. For any two events $ i \neq j $, it is not the case that $ x_i = x_j $ and $ t_i = t_j $. 6. The tourist may remain stationary. 7. The tourist must start at time $ 0 $, and may only move with speed at most $ V $. **Objective** Compute two values: 1. $ M_1 = \max \left\{ |S| : S \subseteq \{1, \dots, N\}, \exists \text{ a path } \gamma : [0, T_{\max}] \to \mathbb{R} \text{ s.t. } \gamma(0) = 0, \|\gamma'\|_\infty \leq V, \text{ and } \forall i \in S, \gamma(t_i) = x_i \right\} $ 2. $ M_2 = \max \left\{ |S| : S \subseteq \{1, \dots, N\}, \exists \text{ a path } \gamma : [0, T_{\max}] \to \mathbb{R} \text{ s.t. } \gamma(0) = p_0' \text{ for some } p_0' \in \mathbb{R}, \|\gamma'\|_\infty \leq V, \text{ and } \forall i \in S, \gamma(t_i) = x_i \right\} $ Output: $ M_1 $ and $ M_2 $

Samples

Input #1

Output #1

1 2

API Response (JSON)

{
  "problem": {
    "name": "F. Tourist",
    "description": {
      "content": "Tourist walks along the _X_ axis. He can choose either of two directions and any speed not exceeding _V_. He can also stand without moving anywhere. He knows from newspapers that at time _t_1 in the p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF76F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tourist walks along the _X_ axis. He can choose either of two directions and any speed not exceeding _V_. He can also stand without moving anywhere. He knows from newspapers that at time _t_1 in the p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "旅游者沿着 #cf_span[X] 轴行走。他可以选择两个方向中的任意一个，以及不超过 #cf_span[V] 的任意速度。他也可以选择原地不动。他从报纸上得知，在时间 #cf_span[t1]、坐标为 #cf_span[x1] 的点将发生一个有趣事件，在时间 #cf_span[t2]、坐标为 #cf_span[x2] 的点将发生另一个事件，依此类推，直到 (#cf_span[xn, tn])。这...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of events.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ (x_i, t_i) \\in \\mathbb{R} \\times \\mathbb{Z}^+ $ denote the coordinate and time of the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments