E. Points, Lines and Ready-made Titles

Codeforces

IDCF872E

Time2000ms

Memory256MB

Difficulty—

graphs

English · Original

Chinese · Translation

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.

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

Samples

Input #1

Output #1

Input #2

2
-1 -1
0 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. 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": "CF872E"
  },
  "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": "给定平面上 #cf_span[n] 个坐标为整数的互不相同的点。对于每个点，你可以选择：过该点画一条竖直线，过该点画一条水平线，或者什么都不做。\n\n你将重合的直线视为同一条。问你能得到多少种不同的图案？请输出答案对 #cf_span[109 + 7] 取模的结果。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 点的数量。\n\n接下来 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments