AtCoder Beginner Contest 139 F: Engines 解説の解説

考察のはじめの一歩が難しかったので記録

全体の方針

エスパーをして，最終的に座標(x,y)にたどり着くのが最適であると知っていたとする．もちろんこのような点は複数ある場合もある．

では最適なゴール(x,y)に辿り着くためには，実際にどのようなベクトルの組み合わせをすれば良いかわかるだろうか？ゴールまでのベクトルgをg=(x,y)とする．あるベクトルとgの内積が正であった場合そのベクトルを採用し，内積が負であった場合そのベクトルを採用しなければよい．

逆にそうしなければ，たどり着いたゴールが原点から最も離れた地点であるという仮定と矛盾する．

では次のような愚直な方針を考える．

ある座標(a,b)が最適なゴールであったとする．このとき，上で述べたようにベクトルを選択する．・・・(1)

選択したベクトルの和が，(a,b)と一致しなかった場合，それは最適なゴールではない．一致した場合，それは最適なゴールだったかもしれない．暫定解として記録しておく. ゴールとしてありえる座標を全探索し，最もスコアが高いものが最適解である．

当然のことながら，ゴールとしてありえる座標の候補は膨大なため，TLEする．しかし，よくよく考えてみると(1)で選択する組み合わせは相当限られてくる．具体的には，ある直線が存在して，その直線の右側区間(or 左側区間)に存在するものを選んだものである．

与えられたベクトルを，偏角でソートしてやれば良い．基本的に外積の正負によってベクトル間の順序を決める比較関数を用いてソートすればよいのだが，これだけだと一周回った付近が全順序集合を満たさないので，どの象限に属しているかの情報を用いる．

ここまで来たらあとはsnukeさんの放送を見ればよい(投げ)