D Campaign Speech
問題\(xy\) 平面上のすべての辺が \(x\) 軸または \(y\) 軸に平行な単純 \(N\) 角形(自己交差や穴のない多角形)が与えられます。
多角形の周上に \(M\) 点の演説場所があります。
この多角形の周上のみ移動可能である時、すべての演説場所を \(1\) 度ずつ訪れるために必要な最短の移動距離を求めてください。
なお、移動の開始地点と終了地点は多角形の周上の好きな位置に設定できます。
\(1\) 行目に多角形の頂点数 \(N\) と演説場所の個数 \(M\) が与えられる。( \(4 \leq N \leq 10^5, 1 \leq M \leq 10^5\) )
\(i+1\) 行目に単純 \(N\) 角形の \(i\) 番目の頂点の座標 \((x_i, y_i)\) が与えられる。( \(1 \leq i \leq N, |x_i| , |y_i| \leq 10^5\) ) 与えられる多角形の辺は \(i\) 番目の頂点と \(i+1\) 番目の頂点を結ぶ。 つまり、 \(x_{i}=x_{i+1}\) または \(y_{i}=y_{i+1}\) のいずれか一方が成り立つ。( \(N+1\) 番目の頂点は \(1\) 番目の頂点を表す。) 辺上に頂点が存在することはない。(角度が \(180\) 度の頂点は存在しない)
\(j + 1 + N\) 行目に \(j\) 番目の演説場所の座標 \((p_j, q_j)\) が与えられる。( \(1 \leq j \leq M, |p_j|, |q_j| \leq 10^5\) ) この点はすべて相異なり、与えられる多角形の周上にある。(頂点上も含む。)
入力はすべて整数で与えられる。
部分点: \(M\) 点の演説場所がすべて単純 \(N\) 角形の頂点上にあるケース全てに正答した場合、 \(1\) 点が与えられる。
答えを出力せよ。
4 30 03 03 20 20 03 03 2
5
6 40 03 03 12 12 20 23 00 22 11 2
5
10 10-12 -11-12 93 93 1-3 1-3 -18 -18 -10-5 -10-5 -113 13 77 -1-3 0-4 -10-12 8-10 -11-3 9-12 -108 -7
74
入力例 \(1\) では、長方形の \(3\) つの頂点上に点があり、 \(1\) 番目 \((0, 0)\) → \(2\) 番目 \((3, 0)\) → \(3\) 番目 \((3, 2)\) の順で訪れると \(3+2=5\) が最短移動距離となる。
入力例 \(1\) の図
入力例 \(2\) の図
入力例 \(3\) の図
