3661: 数数(第二轮03)
题目描述
我们称一个集合 S = {(x1, y1), (x2, y2), … , (xk, yk)}是好的，当且仅当把它们按 照 yi 降序排序后满足：
• 对于所有满足 3 ≤ j ≤ k的 j，有 xj−2 < xj < xj−1或者 xj−1 < xj < xj−2 。
牛牛在二维平面上有一个 n个点的集合。牛牛请你帮他算算有多少个非空子集 S 是好的。因为答案可能很大，你只需要告诉他答案对 10^9 + 7 取模后的结果。
输入
第一行一个整数 n，表示点的个数。
接下来n 行，每行两个整数xi, yi ，表示第 i个点的坐标。
输出
输出一行一个整数表示答案对 10^9 + 7 取模后的结果。
样例输入 复制
4
2 2
3 1
1 4
4 3样例输出 复制
14提示
【样例 1 输入】
4
2 2
3 1
1 4
4 3
【样例 1 输出】
14
【样例 1 说明】
除了 {(2,2),(3,1),(1,4)}以外，其它非空子集均合法。
【样例 2 输入】
18
270154266 674435265
-54662325 -976053549
-17003000 493156492
-122658950 -64114385
64821512 -139450437
-828383768 483137960
-394435024 313278055
-137780421 898227301
-594159382 558373148
-195146551 476698144
228023360 -71588671
-890522860 -549082338
-188398146 934884255
-490250512 969810007
647554795 -294860080
-242692159 709705437
-150243399 -263691260
762072374 698248401
【样例 2 输出】
791
【样例 3 】
选手目录： https://uploadfiles.nowcoder.com/files/20211004/count.zip 见选手目录下的 count/count3.in 和 count/count3.ans。
【数据范围】
对于 8% 的数据，有 1 ≤ n ≤ 18。
对于 20% 的数据，有 1 ≤ n ≤ 100 。
对于 52% 的数据，有 1 ≤ n ≤ 1500。
对于 72% 的数据，有 1 ≤ n ≤ 4000。
对于 100% 的数据， 有 1 ≤ n ≤ 6000， 0 ≤∣ xi ∣, ∣ yi ∣≤ 10^9 。xi 互不相同，yi 互 不相同。