← 返回题目列表

AtCoder · pakencamp_2020_day2_e

E. 抗衰老措施

中文机器翻译题面 查看原题
配点 : 800 点

問題文

帕肯王国的形状是一个无限扩大的二维平面。在帕肯王国 N 路与书 M 有一所房子,i\ (1\leq i\leq N) 真正的路是 它具有由公式 y=a_ix+b_i 表示的直线形状,并且 i\ (1\leq i\leq M) 第三宫是坐标 位于 (x_i,\ y_i) 。

在公园王国,道路老化是一个问题。0 我们选择了不止一条道路进行拆除。路 0 如何选择和拆除多本书 2^N 有多种方法,但对于每种方法 1 计算至少一条未损坏道路上的房屋数量并计算总数。 10^9+7 请求出除以后的余数。


制約

  • 1\leq N,\ M\leq10^5
  • -5×10^4\leq a_i\leq5×10^4
  • 0\leq b_i\leq5×10^4
  • 0\leq x_i,\ y_i\leq5×10^4
  • 所有输入均为整数

小課題

  1. (50 点) N=1
  2. (50 点) N\leq 10,\ M\leq2000
  3. (100 点) M\leq100
  4. (200 点) a_i≠a_j\ (i≠j)
  5. (400 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

\(N\) \(M\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(︙\)
\(a_N\) \(b_N\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(︙\)
\(x_M\) \(y_M\)

出力

总和 除以 10^9+7 求余数。不要忘记输出末尾的换行符。

入力例1

2 2
1 2
2 1
1 3
2 5

出力例1

5

以下是道路被破坏的方式。 4 有一条街。 转至

  1. 1,\ 2 破坏真实的道路。1 第二个房子也是 2 第二个房子也不在路上。
  2. 1 破坏真实的道路。1 第二个房子也是 2 第二个房子也是 2 它位于主干道上。
  3. 2 破坏真实的道路。1 第二个房子是 1 虽然是在主干道上,2 第二个房子不在路上。
  4. 1 书籍也不会破坏道路。1 第二个房子是 1,\ 2 位于主干道上,2 第二个房子也是 2 它位于主干道上。
在所有这些中,满足问题陈述中的条件的房屋总数为 5 ,所以5 。

此示例是一个小作业。 2,\ 3,\ 4,\ 5 约束。

入力例2

2 5
1 3
1 3
2 5
2 5
2 5
2 5
2 5

出力例2

15

此示例是一个小作业。 2,\ 3,\ 5 约束。

入力例3

4 3
1 5
2 3
-1 11
3 2
1 5
3 8
2 7

出力例3

36

此示例是一个小作业。 2,\ 3,\ 4,\ 5 约束。

作者: 企鹅人