G - イノシシ対策
Editorial
/
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
S君は xy 平面上の (X,Y) にある畑で農業を始めることにしました。
しかし、平面上には N 頭のイノシシがいて畑を荒らそうとしています。i 番目のイノシシは (x_i,y_i) に棲んでいます。
S君が対処法を求めて役所に相談したところ、M 個の計画を提案されました。
i 番目の計画は直線 y = a_i x + b_i 上に柵を設置するというもので、実行する場合 2^{i-1} 円かかります。
畑を守るには i=1,2,\ldots,N すべてに対して、(X,Y) と (x_i,y_i) を結ぶ線分(端点含む)とある柵に対応する直線が交点を持つ必要があります。
計画を 0 個以上選んで実行し、畑を守るのに必要な金額の最小値を C 円とします。C を (10^9+7) で割った余りを求めてください。
ただし、どのように計画を選んでも畑を守ることが出来ない場合、代わりに -1
と出力してください。
制約
- 1 \leq N,M \leq 2 \times 10^5
- -10^9 \leq X,Y,x_i,y_i,a_i,b_i \leq 10^9
- (X,Y) \neq (x_i,y_i)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M X Y x_1 y_1 \vdots x_N y_N a_1 b_1 \vdots a_M b_M
出力
答えを出力せよ。
入力例 1
3 3 1 1 2 4 3 9 -5 10 -4 8 3 -3 -7 7
出力例 1
5
1,3 番目の計画を選んで実行するのが最適で、C= 2^{1-1} + 2^{3-1} = 5 であるため、5 を (10^9+7) で割った余りである 5 が期待される出力です。
入力例 2
2 2 0 0 10 3 10 3 5 2 5 2
出力例 2
-1
同じ座標に複数のイノシシが棲んでいる場合や、(必要な金額を除いて)同じ計画が存在する場合があります。