2つの円/円と線分の位置関係 問題解答 ( CodeIQ )

はじめに

CodeIQというところでプログラミング問題「2つの円の位置関係」「円と線分の位置関係」に解答しましたので、ネタバレです。 問題の性質が似ているので、まとめて解説することにします。

codeiq.jp

codeiq.jp

2つの円の位置関係

問題

2つの円の情報の塊が、文字列として数組まとめて与えられるので、位置関係を表すアルファベットに変換して出力する、という問題です。

入力は(1,1)1/(1,20)1 (10,20)10/(20,1000)1 (11,22)3/(22,33)40のように1行で、空白区切りで2円の情報が ( この例だと3組 ) 与えられます。各組は「(中心のX座標,中心のY座標)半径/(中心のX座標,中心のY座標)半径」という構成になっています。なお、数値は全て整数です。

この入力例の場合、円の位置関係を表すアルファベットをつなげて“FFB”と出力するのですが、位置関係とアルファベットの対応は、次の図のようになっています。

f:id:ange1:20160722221517p:plain

解説

一般に、2円の位置関係は、「円の中心間距離」と「半径の和/差」によって測ることができます。 円の中心間距離を$d$、2円の半径を$r_1, r_2$とすると、

位置関係 条件
A 2円が一致 $d=0かつr_1=r_2$
B 一方の円が他方を含む $d\lt|r_1-r_2|$
C 2円が内接 $d=|r_1-r_2|$
D 2円が交わる $|r_1-r_2|\lt d\lt|r_1+r_2|$
E 2円が外接 $d=|r_1+r_2|$
F 2円が共有点を持たない $d\gt|r_1+r_2|$

ですね。なお、A というのは C の特殊な場合になっていることに注意が必要です。

ということで、距離を調べて位置関係を上の表に基づきインデクス化してあげれば良いことになります。提出したコード(Ruby)は次の通りです。

$><<gets.gsub(/\S+ ?/){|m|
  x1,y1,r1,x2,y2,r2=m.scan(/\d+/).map(&:to_i)
  n=(x1-x2)**2+(y1-y2)**2
  ([n==0?0:2,4+(n<=>(r1+r2)**2),1][n<=>(r1-r2)**2]+65).chr
}

これ以上ない素直なコードですね!! なお、変数 n に保持しているのは、距離$d$の平方です。なんで n という名前にしたのかは良く分かりません。

円と線分の位置関係

問題

上の「2つの円の位置関係」と同じく、空白で区切られた情報の塊を、位置関係に対応したアルファベットに変換して出力する問題ですが、今度は円と線分の位置関係です。

したがって、入力される情報も変わってきて、1つの塊は「(円の中心のX座標,中心のY座標)半径/(線分の端点のX座標,端点のY座標)(もう一方の端点のX座標,端点のY座標)」という情報になっています。数値が全て整数なのは上の問題と同じですが、もう一つ条件として、「線分の2端点は一致しない」というのもあります。( 一致しちゃうと線分じゃないですしね )

位置関係の対応は次の図の通りで、例えば(1,1)1/(20,20)(20,21) (10,20)10/(100,100)(100,200) (11,22)100/(22,33)(25,35)という入力に対する出力はIIAとなります。

f:id:ange1:20160722223848p:plain

解説

今度は、2つの円の位置関係と違って、多くの要素が絡んできます。

が、まずは色々名前をつけます。円の中心を O、半径を r、線分の端点の内近い方を N、遠い方を F ( 距離が同じ場合はどっちがどっちでも良い ) とします。
後は、「円の中心から線分におろした垂線の足」も必要になります。これを H とします。

そうすると、距離の比較としては、必ず$OH\le ON\le OF$になります。垂線の長さは、線分への最短距離だからです。そして、H,N,Fが円の内側(in)・周上(on)・外側(out)で分類すると、全部で10通りの状況があります。( 有り得ない組み合わせも含む )

ただ、これだけでは不十分です。あともう一つH,N,Fの順序がどのようになっているか、この情報も必要になってきます。ただ、Hの座標を調べて…というのは実際面倒なので、△ONFにおける∠Nが鋭角か、直角か、鈍角かで判断します。
次の図のように、N,H,Fの順に並ぶのは∠Nが鋭角の時、N,Hが一致するのは ( trivialながら ) ∠Nが直角の時、H,N,Fの順に並ぶのは∠Nが鈍角の時です。Nの方がFよりもOに近いので、N,F,Hの順というのはありません。

f:id:ange1:20160723000428p:plain

ということで、これらの情報をまとめると次の表のようになります。

Hの位置 Nの位置 Fの位置 ∠N鋭角 ∠N直角 ∠N鈍角 備考
in in in A(0) A(0) A(0)
in in on B(1) B(1) B(1)
in in out F(2) F(2) F(2)
in on on C(3) - - 必ずNHFの順になるため、直角・鈍角はない
in on out D(4) - G(5)
in out out E(6) - I(7)
on on on - - - N,H,Fが全て周上で一致となるため起こり得ない
on on out - G(8) - N,Hが周上で一致するため、直角しかない
on out out H(10) - I(12)
out out out I(14) I(14) I(16)

なお、カッコ内の数字は、実際にコードを実装した時に、それぞれの状況に対して振ったインデクスの数値です。注目すべきは分類 I で、in,out,out,鈍角、on,out,out鈍角、out,out,outの主に3種類にわたって同じ分類になっています。I と、あとは G を除くと ( 角度の状況はともかくとして )、点の位置関係が異なれば異なるアルファベット分類になっています。
ちなみに、- は、その状況が起りえないことを指しますが、直角の所が多く - になっているのは、( その状況が起るためには ) H,Nの位置関係 ( in/on/out ) が一致する必要があるためです。

一応、上の表の主要な部分を図示してみました。ちょっと見辛い気もしますが、次のようになります。

f:id:ange1:20160723000349p:plain

最後に…。なんかもう素直過ぎる実装なのでいっか、という気もするのですが、Rubyでの提出コードです。距離の計算と、内積計算による角度の判定を行って、上の表のようなインデクスを作り出し、対応する文字を引いてくる ( I(12),I(14),I(16)は範囲外を検出する形にしている ) というものです。OHの距離は三角形の面積×2÷底辺の長さという分数計算なので、有理数クラスRationalを使っています。便利でいいですね。

$><<gets.gsub(/\S+ ?/){
  r=(c=$&.scan(/\d+/).map(&:to_i)).delete_at(2)
  d2a,d2b,d2l=[0,2,4].combination(2).sort_by{|i,j|i+j}.map{|i,j|[0,1].reduce(0){|s,k|s+(c[i+k]-c[j+k])**2}}
  d2h=Rational([0,2,4].permutation(2).reduce(0){|s,(x,y)|s+c[x]*c[y+1]*((y-x)%6-3)}**2,d2l)
  d2n,d2f=[d2a,d2b].sort
  t=[d2f,d2n,d2h].each_with_index.reduce(7){|s,(d2,i)|s+2**i*(d2<=>r**2)}
  "ABFCDGEIGxH"[t+(d2l+d2n<=>d2f)/2*t/-4]||?I
}

終わりに

高校の時にこういうのやったなあ、と懐かしさを覚える問題でした。条件をきちんと整備するいい訓練になるのではないでしょうか。