CodeIQ：放物線とマス目の関係

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 放物線の頂点の座標
def getPeakPos(a, b, c)
	x = -1*Rational(b, 2*a)
	y = a * (x**2) + b * x + c
	return [x, y]
end

# 放物線の頂点が四角形の内側にあるかを調べる
def isPeakInSquare(peak, x, y)
	if (x < peak[0]) && (peak[0] < x+1) && (y < peak[1]) && (peak[1] < y+1) then
		return true
	else
		return false
	end
end

# 四角形の角座標が放物線の上にあれば+1、下にあれば-1、同じなら0を返す
def checkPosition(a,b,c,x,ys)
	yp = a * (x**2) + b * x + c
	if ys-yp < 0 then return -1
	elsif ys-yp > 0 then return +1
	else return 0
	end
end

# 放物線の上、下、線上にある点の数を数える
def countPointsPos(pos)
	ret = [0,0,0]	# 放物線の上、放物線の下、放物線上

	for v in pos
		if v > 0 then ret[0] += 1
		elsif v < 0 then ret[1] += 1
		else ret[2] += 1
		end
	end

	return ret
end

def solve(a,b,c,x,y)
	peak = getPeakPos(a, b, c)

	# 放物線の頂点が四角形の内側にある場合は必ず"S"になる
	if isPeakInSquare(peak, x, y) then return "S" end

	# 放物線の頂点がX軸に平行な線分上にある場合
	if peak[1] == y+1 then	# 上の線と接している
		if a > 0 then	# 凹側
			return "l"
		elsif a < 0 then	# 凸型
			return "S"
		end
	elsif peak[1] == y then	# 下の線と接している
		if a > 0 then	# 凹側
			return "S"
		elsif a < 0 then	# 凸型
			return "l"
		end
	end

	points = [[0,0], [1,0], [0,1], [1,1]]	# 左下、右下、左上、右上
	pos = []

	for point in points
		pos << checkPosition(a, b, c, x+point[0], y+point[1])
	end

	cnt = countPointsPos(pos)
	if (cnt[0] > 0) && (cnt[1] > 0)	then	# 放物線より上と下の点が1以上ある ＝ 放物線と四角形が交わっている
		return "S"
	elsif (cnt[0] > 0) && (cnt[1] == 0)	&& (cnt[2] == 0) then # 放物線より上の点しかない
		# 放物線の頂点が四角形のX座標の間で下の線よりも上にある
		if ((x < peak[0]) && (peak[0] < x+1)) && (peak[1] > y+1) then
			return "S"
		else
			return "U"
		end
	elsif (cnt[0] == 0) && (cnt[1] > 0)	&& (cnt[2] == 0) then # 放物線より下の点しかない
		# 放物線の頂点が四角形のX座標の間で下の線よりも下にある
		if ((x < peak[0]) && (peak[0] < x+1)) && (peak[1] < y) then
			return "S"
		else
			return "L"
		end
	elsif (cnt[0] > 0) && (cnt[1] == 0)	&& (cnt[2] > 0) then # 放物線より上の点と接点がある
		return "u"
	elsif (cnt[0] == 0) && (cnt[1] > 0)	&& (cnt[2] > 0) then # 放物線より下の点と接点がある
		return "l"
	end

	return "?"
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	a, b, c, x, y = line.split.map{|v| v.to_i}
	puts solve(a,b,c,x,y)
end

解説

ぱっと見は難しそうではなかったのですが、意外と苦労しました。
その上、私のコードには正しく判定できない場合がありそうな気がしています。

雑感

最初、線上で接しているパターンや突き抜いているパターンを考えていなくてリジェクトされました。デバッグにはMacのグラフ計算機が非常に役に立ってくれました。
実のところ、放物線に対して上、下、線上にある四角形の角の数（これは実装している通り）と、四角形の4辺に対して放物線が交わっているかどうかの情報を使えば自信がないなどということはなく、正しく判定できると思うのです。ただ、こちらは四角形のx軸に平行な辺と放物線の交点の有無を調べる時に浮動小数点を使わざるをえない（と思う）ので採用しませんでした。浮動小数点を使わずに交点の有無をうまく判断できる方法があるのでしょうか？