C. Points, Lines and Ready-made Titles

Codeforces

IDCF871C

Time2000ms

Memory256MB

Difficulty—

dfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

You are given _n_ distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it, or do nothing. You consider several coinciding straight lines as a single one. How many distinct pictures you can get? Print the answer modulo 109 + 7. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 105) — the number of points. _n_ lines follow. The (_i_ + 1)-th of these lines contains two integers _x__i_, _y__i_ ( - 109 ≤ _x__i_, _y__i_ ≤ 109) — coordinates of the _i_\-th point. It is guaranteed that all points are distinct. ## Output Print the number of possible distinct pictures modulo 109 + 7. [samples] ## Note In the first example there are two vertical and two horizontal lines passing through the points. You can get pictures with any subset of these lines. For example, you can get the picture containing all four lines in two ways (each segment represents a line containing it). <center>The first way: ![image](https://espresso.codeforces.com/28988446ba734d5927d35c1ff2a90c0ca420c50d.png) The second way: ![image](https://espresso.codeforces.com/dfc652613496b66ba02da6b8aefcd06bd640ece8.png)</center>In the second example you can work with two points independently. The number of pictures is 32 = 9.

给定平面上 n 个横纵坐标均为整数的互不相同的点。对于每个点，你可以选择：过该点画一条竖直线，过该点画一条水平线，或什么都不做。你将重合的直线视为同一条。问你能得到多少种不同的图案？请对 10^9 + 7 取模。第一行包含一个整数 n (1 ≤ n ≤ 10^5) —— 点的数量。接下来 n 行，第 (i + 1) 行包含两个整数 x_i, y_i ( - 10^9 ≤ x_i, y_i ≤ 10^9) —— 第 i 个点的坐标。保证所有点互不相同。请输出可能的不同图案数量，对 10^9 + 7 取模。在第一个例子中，有两条竖直线和两条水平线经过这些点。你可以得到任意这些线的子集构成的图案。例如，包含全部四条线的图案可以通过两种方式得到（每条线段代表包含它的直线）。在第二个例子中，你可以独立处理两个点。图案的数量是 3^2 = 9。 ## Input 第一行包含一个整数 n (1 ≤ n ≤ 10^5) —— 点的数量。n 行follow。第 (i + 1) 行包含两个整数 x_i, y_i ( - 10^9 ≤ x_i, y_i ≤ 10^9) —— 第 i 个点的坐标。保证所有点互不相同。 ## Output 请输出可能的不同图案数量，对 10^9 + 7 取模。 [samples] ## Note 在第一个例子中，有两条竖直线和两条水平线经过这些点。你可以得到任意这些线的子集构成的图案。例如，包含全部四条线的图案可以通过两种方式得到（每条线段代表包含它的直线）。第一种方式：第二种方式：在第二个例子中，你可以独立处理两个点。图案的数量是 3^2 = 9。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of distinct points. Let $ P = \{(x_i, y_i) \mid i \in \{1, \dots, n\}\} $ be the set of points with integer coordinates, all distinct. For each point $ (x_i, y_i) $, we choose one of three actions: - Draw a vertical line at $ x = x_i $, - Draw a horizontal line at $ y = y_i $, - Do nothing. Let $ V = \{x_i \mid \text{vertical line drawn through } (x_i, y_i)\} $ be the set of distinct vertical lines. Let $ H = \{y_i \mid \text{horizontal line drawn through } (x_i, y_i)\} $ be the set of distinct horizontal lines. A *picture* is defined by the pair $ (V, H) $, where coinciding lines are merged. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i $ 3. All points in $ P $ are distinct. **Objective** Compute the number of distinct pictures $ (V, H) $ achievable under the above choices, modulo $ 10^9 + 7 $.

Samples

Input #1

Output #1

Input #2

2
-1 -1
0 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Points, Lines and Ready-made Titles",
    "description": {
      "content": "You are given _n_ distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it, or do nothing. You consider s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF871C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it, or do nothing.\n\nYou consider s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定平面上 n 个横纵坐标均为整数的互不相同的点。对于每个点，你可以选择：过该点画一条竖直线，过该点画一条水平线，或什么都不做。\n\n你将重合的直线视为同一条。问你能得到多少种不同的图案？请对 10^9 + 7 取模。\n\n第一行包含一个整数 n (1 ≤ n ≤ 10^5) —— 点的数量。\n\n接下来 n 行，第 (i + 1) 行包含两个整数 x_i, y_i ( - 10^9 ≤ x_i, y_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of distinct points.  \nLet $ P = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of points with integer coordinates, all distinct.  \n\nF...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments