AT_masters2024_final_a Windy Drone Control (A)

高橋くんは二次元平面上で飛行ドローンを操作し、好きな順番で $ N $ 箇所の目的地を訪れたいと考えている。 東西方向に $ x $ 軸を、南北方向に $ y $ 軸を取る。 飛行区域は $ 2\cdot 10^5\times 2\cdot 10^5 $ の正方形で $ x=-10^5,x=+10^5,y=-10^5,y=+10^5 $ の4つの壁で囲まれている。 更に、これらの外周の壁以外にも内側に壁がある場合がある。 ドローンは位置 $ (x,y) $ と速度 $ (v_x,v_y) $ の状態を持つ。 位置と速度は常に整数値である。 位置 $ (s_x,s_y) $ 、速度 $ (0,0) $ の初期状態から開始し、毎ターン以下の2種類の操作のどちらか一方を行うことが出来る。 1. 加速: 整数ベクトル $ (a_x,a_y) $ を指定し、ドローンの速度を $ (v_x,v_y) $ から $ (v_x+a_x,v_y+a_y) $ に変化させる。 $ a_x^2+a_y^2\leq 500^2 $ を満たす必要がある。 2. 計測: 非零の整数ベクトル $ (b_x,b_y) $ を指定し、現在のドローンの位置 $ (x,y) $ から $ (b_x,b_y) $ 方向に最も近い壁までの距離を誤差付きで計測する。 $ b_x^2+b_y^2\leq 10^{10} $ を満たす必要がある。 $ (x,y) $ から $ (b_x,b_y) $ 方向へ半直線を延ばし( $ (x+b_x,y+b_y) $ を通る)、最初にぶつかった壁の地点 $ (x',y') $ までのユークリッド距離を $ d=\sqrt{(x-x')^2+(y-y')^2} $ とする。得られる値は、入力で与えられるパラメータ $ \delta $ に対し、平均 $ 1 $ 、標準偏差 $ \delta $ の正規分布からサンプルした値を $ \alpha $ として、 $ \mathrm{round}(d\times \alpha) $ である。ただし $ \alpha\leq 0 $ の場合は $ \alpha $ をサンプルし直す。半直線が壁の端点を通る場合はぶつかったと判定される。ただし半直線が壁と平行な場合は除く。 操作後に風の影響でドローンの速度が $ (v_x,v_y) $ からランダムに微少量変化する。 入力で与えられるパラメータ $ \epsilon $ に対し、平均 $ 0 $ 、標準偏差 $ \epsilon $ の正規分布から2つサンプルして四捨五入したものを $ (f_x,f_y) $ としたとき、速度は $ (v_x+f_x,v_y+f_y) $ となる。 各ターンの最後に、その時点での速度 $ (v_x,v_y) $ に応じて、現在位置が $ (x+v_x,y+v_y) $ に更新される。 ただし、二点 $ (x,y) $ と $ (x+v_x,y+v_y) $ を結ぶ線分が、壁と共通部分を持つ場合(線分と壁が平行な場合も含む)、壁に衝突したとして現在位置の更新は行わず、速度を $ (0,0) $ に初期化する。 初期状態でドローンは壁と接していないことが保証されており、壁と衝突時は衝突前の位置に戻るため、壁に接した状態で移動が開始することはない。 壁に衝突しなかった場合、目的地への到達判定を行う。 二点 $ (x,y) $ と $ (x+v_x,y+v_y) $ を結ぶ線分と、まだ訪れていない各目的地 $ (p_x,p_y) $ との距離が $ 1000 $ 以下の場合、その目的地に到達したと判定される。 ここで、線分 $ S $ と点 $ p $ の距離とは、 $ S $ 上の任意の点 $ q $ と $ p $ の距離を考えた時の最小値として定義される。 最大で5000ターンまで操作を行うことが出来、全ての目的地を訪れた時点で操作は即座に完了する。 ### Input & Output Format まずはじめに、以下の形式で標準入力から情報が与えられる。 > $ N $ $ M $ $ \epsilon $ $ \delta $ $ s_x $ $ s_y $ $ p_{x,0} $ $ p_{y,0} $ $ \vdots $ $ p_{x,N-1} $ $ p_{y,N-1} $ $ l_{x,0} $ $ l_{y,0} $ $ r_{x,0} $ $ r_{y,0} $ $ \vdots $ $ l_{x,M-1} $ $ l_{y,M-1} $ $ r_{x,M-1} $ $ r_{y,M-1} $ - 目的地の数は全ての問題において $ N=10 $ で固定である。 - 外周以外の壁の数 $ M $ は $ 0\leq M\leq 10 $ を満たす。 - $ (s_x,s_y) $ はドローンの初期位置を表し、 $ -10^5< s_x,s_y< 10^5 $ を満たす。外周を含む壁と接していないことが保証されている。 - $ (p_{x,i},p_{y,i}) $ は $ i $ 番目の目的地の座標を表し、 $ -10^5\leq p_{x,i},p_{y,i}\leq 10^5 $ を満たす。目的地は壁と接している可能性がある。初期位置ならびに他の目的地との間の距離は $ 5000 $ 以上であることが保証されている。 - $ (l_{x,i},l_{y,i}) $ と $ (r_{x,i},r_{y,i}) $ は $ i $ 番目の壁の端点の座標を表し、 $ -10^5\leq l_{x,i},l_{y,i},r_{x,i},r_{y,i}\leq 10^5 $ を満たす。壁は正の長さを持ち、外周以外の壁とは共通部分を持たないことが保証されている。また、外周との共通部分も1点以下であることが保証されている。これらの条件から、飛行区域内の全ての点は壁を通らずに行き来出来ることが保証される。 上記の情報を読み込んだら、以下の処理を最大で $ 5000 $ ターン繰り返す。 加速を行う場合、加速度ベクトル $ (a_x,a_y) $ を、以下の形式で標準出力に出力せよ。 > A $ a_x $ $ a_y $ 計測を行う場合、計測する方向 $ (b_x,b_y) $ を、以下の形式で標準出力に出力せよ。 > S $ b_x $ $ b_y $ 計測を行った場合のみ、計測結果を表す整数値が標準入力から一行で与えられる。 **出力の後には改行をし、更に標準出力を flush しなければならない。** そうしない場合、TLEとなる可能性がある。 全ての目的地を訪問後および、 $ 5000 $ 回終了後のクエリに対してはジャッジプログラムは返答を行わないため、返答待ちをした場合には TLEとなる可能性があるので注意せよ。 ターンの終わりにドローンの移動結果の情報が以下の形式で標準入力から与えられる。 > $ c $ $ h $ $ q_0 $ $ \cdots $ $ q_{h-1} $ $ c $ は壁に衝突したかどうかを表し、壁に衝突した場合は $ c=1 $ 、しなかった場合は $ c=0 $ である。どの壁に衝突したかの情報は得られない。 $ h $ はこのターンに初めて訪れた目的地の数を表し、次の行の各 $ q_i $ が初めて訪れた目的地の番号 ( $ 0\leq q_i\leq N-1 $ ) である。 $ h=0 $ の場合には、 $ q_i $ の行は空行ではなくスキップされる。 #### 例 $ t $ Output Input 事前情報 ``` 2 0 10.0 0.1 43722 -75332 79243 32532 44002 -77034 ``` 0 ``` A 150 -400 ``` ``` 0 0 ``` 1 ``` S 0 1 ``` ``` 168969 0 1 1 ``` $ \vdots $

N/A

N/A

### 得点 初期状態でスコア $ 0 $ の状態から開始し、毎ターン以下のようにスコアが変動する。 1. スコアが $ 2 $ 減少する。 2. 壁に衝突した場合は追加でスコアが $ 100 $ 減少する。複数の壁に同時に衝突した場合にも減少量は $ 100 $ のみである。 3. 初めて到達した目的地がある場合、1つにつき $ 1000 $ 点が得られる。 5000ターンが経過するもしくは全ての目的地を訪れた時点までのうちで、最もスコアが高かった瞬間のスコアがテストケースに対する得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 各問題に対してコンテスト時間中に得た最高得点の総和で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L,U) $ で表す。 全ての問題で共通な部分を説明する。 各問題固有の部分については下記の「問題毎の違い」を参照せよ。 #### $ s $ の生成 $ s_x=\mathrm{rand}(-99999,99999) $ 、 $ s_y=\mathrm{rand}(-99999,99999) $ により生成される。 #### $ p_{x,i} $ $ p_{y,i} $ の生成 各 $ i $ について順番に、 $ p_{x,i}=\mathrm{rand}(-100000,100000) $ 、 $ p_{y,i}=\mathrm{rand}(-100000,100000) $ により生成し、既に生成した $ s $ や $ (p_{x,j}, p_{y,j}) $ の中にユークリッド距離が 5000 以下のものがあれば生成し直す。 #### 壁の生成 各 $ i $ について順番に以下のように生成する。 まず、 $ l_{x,i}=\mathrm{rand}(-90000,90000) $ 、 $ l_{y,i}=\mathrm{rand}(-90000,90000) $ を生成し、次に $ r_{x,i}'=l_{x,i}+\mathrm{rand}(-100000,100000) $ 、 $ r_{y,i}'=l_{y,i}+\mathrm{rand}(-100000,100000) $ と設定する。 $ (l_{x,i},l_{y,i})=(r_{x,i}',r_{y,i}') $ の場合は $ i $ 番の壁の生成をやり直す。 $ r_{x,i}' $ が範囲外 ( $ r_{x,i}'