CodeIQ：２つの円の位置関係

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「２つの円の位置関係」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
円が２つあります。
２つの円の関係は、下表のいずれかになります。
記号 説明 状態の例
A ２つの円は、半径も中心も同じです。 略
B 一方の円が、他方の円を完全に含んでいます。
C 一方の円が、他方の円に内接しています。
D 互いに一部を共有しています。
E 互いに外接しています。
F ２つの円は共有点を持ちません。

【入出力】
入力は
(1,1)1/(1,20)1 (10,20)10/(20,1000)1 (11,22)3/(22,33)40
のような感じです。

「(中心のX座標,中心のY座標)半径/(中心のX座標,中心のY座標)半径」という形式で書かれた円のペアが、空白区切りで並んでいます。

出力は、各ペアが前述の A〜F のどれに該当するのかを、区切り文字なしで並べたものです。

先程の例だと
最初のペア(1,1)1/(1,20)1は、共有点を持たないので F
二番目のペア(10,20)10/(20,1000)1も、共有点を持たないので F
最後のペア(11,22)3/(22,33)40は、半径40の方が半径3の方を完全に含んでいるので B

ということで、
FFB
と出力すれば正解となります。
末尾の改行はあってもなくても構いません。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 円クラス
class Circle
	def initialize(x, y, r)
		@x = x
		@y = y
		@r = r
	end

	attr_accessor :x, :y, :r
end

# 入力値をパースする
# [[a1,a2],[b1,b2], ...]でa,bはCircleのインスタンス
def parseInput(line)
	arr = line.split(" ")
	ret = []

	for pair in arr
		vals = []
		splited = pair.split("/")

		for c in splited
			x,y,r = c.gsub("(", "").gsub(")", ",").split(",").map{|v| v.to_i}
			vals.push(Circle.new(x,y,r))
		end

		ret.push(vals)
	end

	return ret
end

# 2つの円の距離をチェックする
# a,bはCircleのインスタンス
def checkDistance(a, b)
	if (a.x == b.x) && (a.y == b.y) && (a.r == b.r) then return "A" end

	doo = (a.x-b.x)**2 + (a.y-b.y)**2
	max_r = (a.r-b.r) >= 0 ? a.r : b.r

	if doo < max_r**2 then	# 中心間の距離が大きい方の半径よりも短い
		drr = a.r - b.r

		if doo < drr**2 then return "B"		# 中心間の距離が半径の差よりも小さい（内包する）
		elsif doo == drr**2 then return "C"	# 中心間の距離が半径の差に等しい（内接する）
		else return "D"						# 一部を共有する
		end
	else # 中心間の距離が大きい方の半径よりも長いか等しい
		drr = a.r + b.r

		if doo > drr**2 then return "F"		# 中心間の距離が半径の和よりも大きい（離れている）
		elsif doo == drr**2 then return "E"	# 中心間の距離が半径の和に等しい（外接する）
		else return "D"						# 一部を共有する
		end
	end
end

#main
while line = gets
	circles = parseInput(line.strip)
end

ret = ""
for cp in circles
	ret += checkDistance(cp[0], cp[1])
end

puts ret

解説

割と難しい（というか面倒臭い）です。ですが高校レベルの数学なのでやればできます。
入力値のパースが面倒ですが問題の本題には関係ないので説明しません。

Circleクラス

円の中心座標と半径を保持するクラスです。メンバ関数を1つも持っていないのでC言語で言うところの構造体的な使い方をします。Pythonのようにタプルがあればタプルを使いましたがRubyの場合、配列で表現しなければならず[カッコ]がいっぱいになるのでクラスを作りました。

checkDistance

2つの円の距離をチェックする関数でプログラムの本体です。

まず、中心と半径が一致する場合、円は重なるのでAを返します。

次に、2つの円の中心間の距離（の2乗）と大きい方の半径を求めます。
変数dooが2つの円の中心間の距離（の2乗）で、max_rが大きい方の半径です。
dooの平方根を求めれば半径になりますが浮動小数点で扱いたくないので2乗の値のままで処理します。

中心間の距離が大きい方の半径より小さい場合、2つの円の位置関係はB、C、Dのどれかになります。このうちのどれになるかは2つの円の半径の差を求めることでわかります。
2つの円の中心間の距離が半径の差よりも小さい場合、一方の円が他方を内包します。
2つの円の中心間の距離が半径の差と等しい場合、内接します。
それ以外の場合は一部を共有します。

中心間の距離が大きい方の半径よりも長いか等しい場合、2つの円の位置関係はD、E、Fのどれかになります。このうちのどれになるかは2つの円の半径の和を求めることでわかります。
2つの円の中心間の距離が半径の和よりも大きい場合、2つの円は離れています。
2つの円の中心間の距離が半径の和と等しい場合、外接します。
それ以外の場合は一部を共有します。

雑感

図を見ながら真面目に場合分けすればできると思います。
この問題は同日公開された「円と線分の位置関係」の肩慣らし的な問題と思います。