{"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 vertical line;\n*   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.\n\nYou 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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.\n\nAll points in the superset should have integer coordinates.\n\n[samples]","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_span[1 ≤ n ≤ 104]) —— 初始集合中点的数量。接下来的 #cf_span[n] 行描述该集合的点。每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 对应点的坐标。保证所有点互不相同。\n\n请在第一行输出 good 超集中点的数量 #cf_span[m] (#cf_span[n ≤ m ≤ 2·105])，然后在接下来的 #cf_span[m] 行中输出这些点。点的坐标绝对值不应超过 #cf_span[109]。注意，你无需最小化 #cf_span[m]，只需找到任意一个满足大小不超过 #cf_span[2·105] 的 good 超集即可。\n\n超集中所有点的坐标必须为整数。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— 初始集合中点的数量。接下来的 #cf_span[n] 行描述该集合的点。每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 对应点的坐标。保证所有点互不相同。\n\n## Output\n\n请在第一行输出 good 超集中点的数量 #cf_span[m] (#cf_span[n ≤ m ≤ 2·105])，然后在接下来的 #cf_span[m] 行中输出这些点。点的坐标绝对值不应超过 #cf_span[109]。注意，你无需最小化 #cf_span[m]，只需找到任意一个满足大小不超过 #cf_span[2·105] 的 good 超集即可。超集中所有点的坐标必须为整数。\n\n[samples]","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 points $ a, b \\in S $, at least one of the following holds:  \n1. $ a_x = b_x $ (same x-coordinate),  \n2. $ a_y = b_y $ (same y-coordinate),  \n3. $ |a_x - b_x| = |a_y - b_y| $ (points lie on a diagonal of slope ±1).\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^4 $  \n2. For each $ p_i = (x_i, y_i) \\in P $: $ -10^9 \\le x_i, y_i \\le 10^9 $  \n3. All points in $ P $ are distinct.  \n4. The output superset $ S \\supseteq P $ must satisfy:  \n   - $ n \\le |S| \\le 2 \\cdot 10^5 $  \n   - All points in $ S $ have integer coordinates with absolute value $ \\le 10^9 $\n\n**Objective**  \nFind any good superset $ S \\supseteq P $ satisfying the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF97B","tags":["constructive algorithms","divide and conquer"],"sample_group":[["2\n1 1\n2 2","3\n1 1\n2 2\n1 2"]],"created_at":"2026-03-03 11:00:39"}}