B. Rectangles

Codeforces

IDCF10196B

Time2000ms

Memory256MB

Difficulty—

You are given $2 n$ points, you need to pair them to create $n$ rectangles so that the intersection of all those rectangles forms a positive area. In how many ways you can do that? Find the number of ways modulo $10^9 + 7$. Pairing two points ($x 1, y 1$) and ($x 2, y 2$) forms the rectangle with bottom-left corner ($m i n (x 1, x 2), m i n (y 1, y 2)$) and top-right corner ($m a x (x 1, x 2), m a x (y 1, y 2)$). The first line of input contains a single integer $T$ ($1 <= T <= 3200$), the number of test cases. The first line of each test case contains a single integer $n$ ($1 <= n <= 10^5$), the number of rectangles you need to make. The following $2 n$ lines each contains two space-separated integers $x_i, y_i$ ($-10^9 <= x_i, y_i <= 10^9$), representing the coordinates of the $i^(t h)$ point. All points are distinct. The sum of $n$ over all test cases doesn't exceed $5 times 10^5$. For each test case output a single line with the number of ways to pair the $2 n$ points modulo $10^9 + 7$. ## Input The first line of input contains a single integer $T$ ($1 <= T <= 3200$), the number of test cases.The first line of each test case contains a single integer $n$ ($1 <= n <= 10^5$), the number of rectangles you need to make.The following $2 n$ lines each contains two space-separated integers $x_i, y_i$ ($-10^9 <= x_i, y_i <= 10^9$), representing the coordinates of the $i^(t h)$ point. All points are distinct.The sum of $n$ over all test cases doesn't exceed $5 times 10^5$. ## Output For each test case output a single line with the number of ways to pair the $2 n$ points modulo $10^9 + 7$. [samples]

API Response (JSON)

{
  "problem": {
    "name": "B. Rectangles",
    "description": {
      "content": "You are given $2 n$ points, you need to pair them to create $n$ rectangles so that the intersection of all those rectangles forms a positive area. In how many ways you can do that? Find the number of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10196B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given $2 n$ points, you need to pair them to create $n$ rectangles so that the intersection of all those rectangles forms a positive area. In how many ways you can do that? Find the number of ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments