AT_tenka1_2013_final_e 天下一折れ線遊戯

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_e $ x $ 座標の正の方向を右、$ y $ 座標の正の方向を上とします。 紙の上に、 - 左の方に $ N $ 個の赤い点 $ (0,\ 0),\ (0,\ 1000),\ ...,\ (0,\ 1000(N-1)) $ - 右の方に $ N $ 個の青い点 $ (10^9,\ 0),\ (10^9,\ 1000),\ ...,\ (10^9,\ 1000(N-1)) $ - $ M $ 個の黒い点 $ (X_k,\ Y_k) $ があります。黒い点の $ x $ 座標は全て異なります。 高橋くんは折れ線が大好きです。 それぞれの点 $ (x_k,\ y_k) $ について、 - 何もしない - $ x\ >\ x_k,\ y\ >\ y_k $の領域にある点の中で、 $ y $ 座標の値が最も小さい点と線分でつなぐ。そのような点が複数あるなら最も近い点と線分でつなぐ。そのような点がないなら何もしない。 - $ x\ >\ x_k,\ y\ の領域にある点の中で、\ y $ 座標の値が最も大きい点と線分でつなぐ。そのような点が複数あるなら最も近い点と線分でつなぐ。そのような点がないなら何もしない。 - $ x\ >\ x_k,\ y\ =\ y_k $の領域にある点の中で、最も近い点と線分でつなぐ。そのような点がないなら何もしない。 のどれか $ 1 $ つを行います。 高橋くんは、全ての赤い点に対して、折れ線でちょうど $ 1 $ つの青い点と結ばれるようにしたいです。 それぞれの折れ線は交わったり触れたりしてはいけません。また、 $ N $ 個の折れ線に含まれない無駄な線分を引いてもいけません。 $ N $ 個の折れ線の引き方は何通りあるかを mod $ 1000000007 $ で求めてください。 入力は、以下の形式で与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : $ X_M $ $ Y_M $ 1. $ 1 $ 行目には、赤い点と青い点の数 $ N\ (1\ ≦\ N\ ≦\ 3) $ と、黒い点の数 $ M\ (0\ ≦\ M\ ≦\ 100000) $ が、 $ 1 $ 行で入力される 2. $ 2 $ 行目から $ M+1 $ 行までの $ M $ 行では、$ i $ 番目の黒い点の $ x $ 座標と $ y $ 座標を表す整数 $ X_i,\ Y_i\ (0\ が与えられる。 黒い点の\ x $ 座標は互いに異なります。つまり、$ i\ \neq\ j $ のとき、$ X_i\ \neq\ X_j $ を満たします。 - $ N\ =\ 1 $の入力に正解すると、$ 320 $ 点満点に対して部分点として $ 60 $ 点が与えられる。 - $ 0\ ≦\ M\ ≦\ 40 $ の入力に正解すると、$ 320 $ 点満点に対して部分点として上記とは別に $ 60 $ 点が与えられる。 高橋君が引くことが出来る、 $ N $ 個の折れ線の引き方は何通りあるかを、出力しなさい。もし組み合わせが $ 1000000007 $ 通り以上であった場合は、 $ 1000000007 $ で割った余りを出力しなさい。 また、出力の最後には改行をいれること。 ``` 2 2 100 100 110 110 ``` ``` 5 ``` $ (0,\ 0) $ が1つ目の赤い点（赤1）、$ (0,\ 1000) $ が2つ目の赤い点（赤2）、 $ (1000000000,\ 0) $ が1つ目の青い点（青1）、$ (1000000000,\ 1000) $ が2つ目の青い点（青2）、 $ (100,\ 100) $ が1つ目の黒い点（黒1）、$ (110,\ 110) $ が2つ目の黒い点（黒2）、と合計で $ 6 $ 個の点があります。 - 赤1から線分を引けるのは黒1または青1のみ、 - 赤2から線分を引けるのは黒2または青2のみ、 - 黒1から線分を引けるのは黒2または青1のみ、 - 黒2から線分を引けるのは青1または青2のみ となります。 交わったり、触れたりせずに折れ線を2個作るには - （赤1 - 黒1 - 黒2 - 青1、赤2 - 青2） - （赤1 - 黒1 - 青1、赤2 - 黒2 - 青2） - （赤1 - 黒1 - 青1、赤2 - 青2） - （赤1 - 青1、赤2 - 黒2 - 青2） - （赤1 - 青1、赤2 - 青2） と $ 5 $ 通りの方法があります。 ``` 1 3 500 800 300 500 400 400 ``` ``` 3 ``` $ (0,\ 0) $ が1つ目の赤い点（赤1）、 $ (1000000000,\ 0) $ が1つ目の青い点（青1）、 $ (500,\ 800) $ が1つ目の黒い点（黒1）、$ (300,\ 500) $ が2つ目の黒い点（黒2）、$ (400,\ 400) $ が3つ目の黒い点（黒3）と合計で $ 5 $ 個の点があります。 - 赤1から線分を引けるのは黒3または青1のみ、 - 黒1から線分を引けるのは青1のみ、 - 黒2から線分を引けるのは黒1または黒3のみ、 - 黒3から線分を引けるのは黒1または黒2のみ となります。 赤1と青1をつなぐ折れ線を作るには - （赤1 - 青1） - （赤1 - 黒3 - 青1） - （赤1 - 黒3 - 黒1 - 青1） と $ 3 $ 通りの方法があります。 ``` 2 2 1000 0 2000 1000 ``` ``` 1 ``` 赤い点を下から赤1、赤2、 青い点を下から青1、青2、 黒い点を入力で与えられた順番に黒1、黒2とします。 - （赤1 - 黒1 - 青1、赤2 - 黒2 - 青2） と $ 1 $ 通りの方法しかありません。 ``` 3 8 500 5000 3500 5000 2000 3500 1500 2000 2500 2000 1000 1000 3000 1000 1 1 ``` ``` 48 ``` ``` 3 0 ``` ``` 1 ``` それぞれの赤い点は、まっすぐ右にある青い点と結びます。 それぞれの折れ線は交差できないため、これ以外の引き方はありません。

N/A

N/A