|
立命館合宿3日目のFでジャッジ解を撃墜したので僕が反射点を求めた解法を書いておきます。
点Aから円C上の点Rに向けて弾を撃つと点Bに到達するような点Rを求めたい。
円Cの上の点をR'とするとAR+BR<=AR'+BR'が成り立つ。(1)
候補となる点は点Aを通る円Cの接線の円との共有点2つの間にある。
この2点の間をR'を動かすとAR'+BR'は下に凸な関数になる。(2)
よって3分探索でAR'+BR'が最小となるR'を求めるとそれが点Rである。
AP+BP=Xとするとこれを満たす点Pの集合はA,Bを焦点とする楕円となる。
(1)
楕円と円Cが外側で接する時、接点は明らかに点Rである。
楕円の外の点QについてAR+BR＜AQ+BQが成り立つ。
円C上の点R'はR=R'を除いて楕円の外なのでAR+BR<=AR'+BR'である。
(2)
楕円と円Cが共有点を持つようなXの最小値、最大値をX1,X2とする。
AR'+BR'=X1の時、R'=Rとなるのでこれは2つの接点の間に存在する。
AR'+BR'=X2の時、R'が2つの接点の間に存在するとしたら直線AR'は円と2つの交点を持つ。
R'ではない方の交点をR"とするとAR"+BR"=AR'+R'R"+BR"。
三角不等式よりR'R"+BR">BR'であるのでAR"+BR">AR'+BR'。
これはX2がAR'+BR'の最大値であることに反する。
したがって、AR'+BR'=X2の時、R'は2つの接点の間にない。
よってAR'+BR'の値をX1から大きくしていくと、円と楕円の交点はRからそれぞれ左右に移動し途中で逆に動くことはない。
以上から接点の間でR'を動かすとAR'+BR'は下に凸な関数になる。
接点の間を探索するのではなく円Cと線分AO,BO(点Oは円Cの中心)の交点の間を探索したほうが実装が楽になりそうです。
Respect2D2013/03/14 16:57撃墜ありがとうございます。解説を参考にジャッジデータを作り直します。
not5222013/03/14 18:58反射する弾丸の軌跡に接する円が上下ともにあれば正しく反射させられていない解答は落とせると思います。
