M. Quadcopter Competition

Codeforces

IDCF883M

Time3000ms

Memory256MB

Difficulty—

greedymath

English · Original

Chinese · Translation

Formal · Original

Polycarp takes part in a quadcopter competition. According to the rules a flying robot should: * start the race from some point of a field, * go around the flag, * close cycle returning back to the starting point. Polycarp knows the coordinates of the starting point (_x_1, _y_1) and the coordinates of the point where the flag is situated (_x_2, _y_2). Polycarp’s quadcopter can fly only parallel to the sides of the field each tick changing exactly one coordinate by 1. It means that in one tick the quadcopter can fly from the point (_x_, _y_) to any of four points: (_x_ - 1, _y_), (_x_ + 1, _y_), (_x_, _y_ - 1) or (_x_, _y_ + 1). Thus the quadcopter path is a closed cycle starting and finishing in (_x_1, _y_1) and containing the point (_x_2, _y_2) strictly inside. <center>![image](https://espresso.codeforces.com/da2c34a6ad8af23bf3b7b8ec3313972f04631415.png) The picture corresponds to the first example: the starting (and finishing) point is in (1, 5) and the flag is in (5, 2).</center>What is the minimal length of the quadcopter path? ## Input The first line contains two integer numbers _x_1 and _y_1 ( - 100 ≤ _x_1, _y_1 ≤ 100) — coordinates of the quadcopter starting (and finishing) point. The second line contains two integer numbers _x_2 and _y_2 ( - 100 ≤ _x_2, _y_2 ≤ 100) — coordinates of the flag. It is guaranteed that the quadcopter starting point and the flag do not coincide. ## Output Print the length of minimal path of the quadcopter to surround the flag and return back. [samples]

Polycarp 参加了一场四轴飞行器比赛。根据规则，飞行机器人必须： Polycarp 知道起点 (#cf_span[x1, y1]) 的坐标和旗帜所在点 (#cf_span[x2, y2]) 的坐标。Polycarp 的四轴飞行器每次只能平行于场地边移动，每 Tick 恰好改变一个坐标值 #cf_span[1]。这意味着在一次 Tick 中，四轴飞行器可以从点 (#cf_span[x, y]) 飞到以下四个点中的任意一个：(#cf_span[x - 1, y])、(#cf_span[x + 1, y])、(#cf_span[x, y - 1]) 或 (#cf_span[x, y + 1])。因此，四轴飞行器的路径是一个闭合环路，起点和终点均为 (#cf_span[x1, y1])，且点 (#cf_span[x2, y2]) 严格位于该环路内部。求四轴飞行器路径的最小长度。第一行包含两个整数 #cf_span[x1] 和 #cf_span[y1] (#cf_span[ - 100 ≤ x1, y1 ≤ 100]) —— 四轴飞行器的起点（也是终点）坐标。第二行包含两个整数 #cf_span[x2] 和 #cf_span[y2] (#cf_span[ - 100 ≤ x2, y2 ≤ 100]) —— 旗帜的坐标。保证四轴飞行器的起点与旗帜位置不重合。请输出四轴飞行器绕行旗帜并返回起点的最小路径长度。 ## Input 第一行包含两个整数 #cf_span[x1] 和 #cf_span[y1] (#cf_span[ - 100 ≤ x1, y1 ≤ 100]) —— 四轴飞行器的起点（也是终点）坐标。第二行包含两个整数 #cf_span[x2] 和 #cf_span[y2] (#cf_span[ - 100 ≤ x2, y2 ≤ 100]) —— 旗帜的坐标。保证四轴飞行器的起点与旗帜位置不重合。 ## Output 请输出四轴飞行器绕行旗帜并返回起点的最小路径长度。 [samples]

**Definitions** Let $ (x_1, y_1) \in \mathbb{Z}^2 $ be the starting (and ending) point of the quadcopter. Let $ (x_2, y_2) \in \mathbb{Z}^2 $ be the flag point, with $ (x_1, y_1) \neq (x_2, y_2) $. **Constraints** The quadcopter moves only along grid lines (Manhattan steps): from $ (x, y) $ to one of $ (x\pm1, y) $, $ (x, y\pm1) $. The path must be a closed cycle starting and ending at $ (x_1, y_1) $, and the point $ (x_2, y_2) $ must lie strictly inside the region enclosed by the path. **Objective** Find the minimal length of such a closed path. $$ \text{Minimal path length} = 2 \cdot \left( |x_1 - x_2| + |y_1 - y_2| + 2 \right) $$

Samples

Input #1

1 5
5 2

Output #1

Input #2

0 1
0 0

Output #2

API Response (JSON)

{
  "problem": {
    "name": "M. Quadcopter Competition",
    "description": {
      "content": "Polycarp takes part in a quadcopter competition. According to the rules a flying robot should: *   start the race from some point of a field, *   go around the flag, *   close cycle returning back to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF883M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp takes part in a quadcopter competition. According to the rules a flying robot should:\n\n*   start the race from some point of a field,\n*   go around the flag,\n*   close cycle returning back to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 参加了一场四轴飞行器比赛。根据规则，飞行机器人必须：\n\nPolycarp 知道起点 (#cf_span[x1, y1]) 的坐标和旗帜所在点 (#cf_span[x2, y2]) 的坐标。Polycarp 的四轴飞行器每次只能平行于场地边移动，每 Tick 恰好改变一个坐标值 #cf_span[1]。这意味着在一次 Tick 中，四轴飞行器可以从点 (#cf_span[x, y]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ (x_1, y_1) \\in \\mathbb{Z}^2 $ be the starting (and ending) point of the quadcopter.  \nLet $ (x_2, y_2) \\in \\mathbb{Z}^2 $ be the flag point, with $ (x_1, y_1) \\neq (x_2, y_2) $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments