位置関係2題の解説・解題
先日、CodeIQ に出していた
- 2つの円の位置関係( https://codeiq.jp/q/2785 )
- 円と線分の位置関係( https://codeiq.jp/q/2786 )
という2つの問題が締め切られた。
私が出した問題が締め切られるのは久々だったので、ちょっと慣れない感じ。
で。
この問題は、タイトルの通り、2つの図形の位置関係を分類する問題になっている。
2つの円の方は、中心と中心の距離を見ればいいだけなので簡単。
円と線分はいろいろ見なくちゃいけないし、分類も多いのでちょっと大変、ということになっている。
数学力はあまり問うていないつもり。高校程度なんだと思う。
いつもなら、一つの事象をひとつのテストデータにするんだけど、今回はそれだと件数が多くなりすぎる感じなので、ひとつのテストデータにたくさんの事象を仕込むことにした。
問題の概要については
http://ange1.hateblo.jp/entry/2016/07/23/001128
をご覧いただくことにして、出題意図を列挙すると。
というつもり。浮動小数点を使っても解決できてしまう場合が多かったようで、この点はテストデータの追い込みが足りなかったと反省している。
「接する」というデリケートな条件を判断する必要がある問題になっているので、誤差がまったくない計算をする必要がある。そして、この問題はそのような実装を無理なくできる問題になっている。入力は整数だし。
誤差のない計算ということで、有理数が簡単に扱える ruby や python だと実装が楽になる。
JavaScript だと苦しい感じかもしれない。
私の場合はやっぱり ruby でこんな感じ:
2つの円の位置関係の実装例:
def solve_one(s) x0,y0,r0,x1,y1,r1 = s.scan( /\d+/ ).map(&:to_i) d2 = (x0-x1)**2 + (y0-y1)**2 r0,r1=[r0,r1].minmax return "A" if d2==0 && r0==r1 sr2 = (r0+r1)**2 return "F" if sr2<d2 return "E" if sr2==d2 dr2=(r1-r0)**2 return "B" if d2<dr2 return "C" if d2==dr2 return "D" if d2>dr2 raise "unexpected" end def solve( src ) src.split(" ").map{ |s| solve_one( s ) }.join("") end puts solve(gets)
円と線分の位置関係の実装例:
def calc_min2( a, b, c ) candidates=[ c, # x==0 a+b+c # x==1 ] x=-b/2.to_r/a candidates.push( a*x*x+b*x+c ) if 0<=x && x<=1 candidates.min end def solve_one(s) cx,cy,r,ax,ay,bx,by = s.scan( /\d+/ ).map(&:to_r) ax-=cx ay-=cy bx-=cx by-=cy a=ax*ax+ay*ay<=>r*r b=bx*bx+by*by<=>r*r return "A" if a<0 && b<0 return "C" if a==0 && b==0 return "B" if a<=0 && b<=0 return "F" if a*b<0 vx=bx-ax vy=by-ay min2 = calc_min2(vx*vx+vy*vy, 2*(ax*vx+ay*vy), ax*ax+ay*ay ) case min2<=>r*r when -1; a*b==0 ? "D": "E" when 0; a*b==0 ? "G": "H" when 1; "I" end end def solve( src ) src.split(" ").map{ |s| solve_one( s ) }.join("") end puts solve(gets)
我ながらもう少しなんとかならなかったのかと思わなくもない。
ともあれ。
多くの方に挑戦いただき大変うれしく思っています。ありがとうございました。