B. Superset

Codeforces

IDCF97B

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdivide and conquer

English · Original

Chinese · Translation

Formal · Original

A set of points on a plane is called good, if for any two points at least one of the three conditions is true: * those two points lie on same horizontal line; * those two points lie on same vertical line; * the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points. You are given a set consisting of _n_ points on a plane. Find any good superset of the given set whose size would not exceed 2·105 points. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 104) — the number of points in the initial set. Next _n_ lines describe the set's points. Each line contains two integers _x__i_ and _y__i_ ( - 109 ≤ _x__i_, _y__i_ ≤ 109) — a corresponding point's coordinates. It is guaranteed that all the points are different. ## Output Print on the first line the number of points _m_ (_n_ ≤ _m_ ≤ 2·105) in a good superset, print on next _m_ lines the points. The absolute value of the points' coordinates should not exceed 109. Note that you should not minimize _m_, it is enough to find any good superset of the given set, whose size does not exceed 2·105. All points in the superset should have integer coordinates. [samples]

平面上的一组点被称为 #cf_span(class=[tex-font-style-underline], body=[good])，当且仅当对于任意两点，以下三个条件中至少有一个成立：给定平面上由 #cf_span[n] 个点组成的集合。请找出一个包含该集合的 good 超集，其大小不超过 #cf_span[2·105] 个点。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— 初始集合中点的数量。接下来的 #cf_span[n] 行描述该集合的点。每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 对应点的坐标。保证所有点互不相同。请在第一行输出 good 超集中点的数量 #cf_span[m] (#cf_span[n ≤ m ≤ 2·105])，然后在接下来的 #cf_span[m] 行中输出这些点。点的坐标绝对值不应超过 #cf_span[109]。注意，你无需最小化 #cf_span[m]，只需找到任意一个满足大小不超过 #cf_span[2·105] 的 good 超集即可。超集中所有点的坐标必须为整数。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— 初始集合中点的数量。接下来的 #cf_span[n] 行描述该集合的点。每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 对应点的坐标。保证所有点互不相同。 ## Output 请在第一行输出 good 超集中点的数量 #cf_span[m] (#cf_span[n ≤ m ≤ 2·105])，然后在接下来的 #cf_span[m] 行中输出这些点。点的坐标绝对值不应超过 #cf_span[109]。注意，你无需最小化 #cf_span[m]，只需找到任意一个满足大小不超过 #cf_span[2·105] 的 good 超集即可。超集中所有点的坐标必须为整数。 [samples]

**Definitions** Let $ P = \{p_1, p_2, \dots, p_n\} \subset \mathbb{Z}^2 $ be a set of $ n $ distinct points in the plane. A set $ S \subset \mathbb{Z}^2 $ is called *good* if for any two distinct points $ a, b \in S $, at least one of the following holds: 1. $ a_x = b_x $ (same x-coordinate), 2. $ a_y = b_y $ (same y-coordinate), 3. $ |a_x - b_x| = |a_y - b_y| $ (points lie on a diagonal of slope ±1). **Constraints** 1. $ 1 \le n \le 10^4 $ 2. For each $ p_i = (x_i, y_i) \in P $: $ -10^9 \le x_i, y_i \le 10^9 $ 3. All points in $ P $ are distinct. 4. The output superset $ S \supseteq P $ must satisfy: - $ n \le |S| \le 2 \cdot 10^5 $ - All points in $ S $ have integer coordinates with absolute value $ \le 10^9 $ **Objective** Find any good superset $ S \supseteq P $ satisfying the above constraints.

Samples

Input #1

2
1 1
2 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "B. Superset",
    "description": {
      "content": "A set of points on a plane is called good, if for any two points at least one of the three conditions is true: *   those two points lie on same horizontal line; *   those two points lie on same verti",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF97B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A set of points on a plane is called good, if for any two points at least one of the three conditions is true:\n\n*   those two points lie on same horizontal line;\n*   those two points lie on same verti...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "平面上的一组点被称为 #cf_span(class=[tex-font-style-underline], body=[good])，当且仅当对于任意两点，以下三个条件中至少有一个成立：\n\n给定平面上由 #cf_span[n] 个点组成的集合。请找出一个包含该集合的 good 超集，其大小不超过 #cf_span[2·105] 个点。\n\n第一行包含一个整数 #cf_span[n] (#cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} \\subset \\mathbb{Z}^2 $ be a set of $ n $ distinct points in the plane.  \nA set $ S \\subset \\mathbb{Z}^2 $ is called *good* if for any two distinct ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments