{"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 ways modulo $10^9 + 7$.\n\nPairing 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)$).\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 3200$), the number of test cases.\n\nThe first line of each test case contains a single integer $n$ ($1 <= n <= 10^5$), the number of rectangles you need to make.\n\nThe 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.\n\nThe sum of $n$ over all test cases doesn't exceed $5 times 10^5$.\n\nFor each test case output a single line with the number of ways to pair the $2 n$ points modulo $10^9 + 7$.\n\n## Input\n\nThe 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$.\n\n## Output\n\nFor each test case output a single line with the number of ways to pair the $2 n$ points modulo $10^9 + 7$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"CF10196B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}