私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「三角形と点の関係」（CodeIQ）を参照してください。
【概要】
三角形と点があります。
三角形と点の位置関係は、下表のいずれかになります：
記号 説明 A 点は、三角形の内側にあります。 B 点は、三角形の辺上にありますが、頂点上ではありません。 C 点は、三角形の頂点にあります。 D 点は、三角形の外側にあります。
どの関係になるのかを求めるプログラムを書いて下さい。
【入出力】
入力は
(1,1)(10,1)(1,10)/(2,2) (1,2)(1,1)(2,1)/(12,34) (1,3)(3,1)(4,4)/(2,2)
こんな感じです。
三角形と点の組が空白区切りで並んでいます。
スラッシュの前が三角形です。() 内に、頂点のx座標y座標がコンマ区切りで並んでいます。スラッシュの後は点の座標です。
出力は、各組が前述の A〜D のどれに該当するのかを区切り文字なしで並べたものです。
先程の例だと
最初の組(1,1)(10,1)(1,10)/(2,2)の関係は、A。
二番目の組(1,2)(1,1)(2,1)/(12,34)の関係は、D。
最後の組(1,3)(3,1)(4,4)/(2,2)の関係は、B。
ということで、ADBを出力すれば正解となります。
末尾の改行はあってもなくても構いません。
【例】
入力 出力 (1,1)(10,1)(1,10)/(2,2) (1,2)(1,1)(2,1)/(12,34) (1,3)(3,1)(4,4)/(2,2)ADB(10,200)(10,10)(123,10)/(4,5) (12,35)(31,12)(41,44)/(41,44)DC
【補足】
座標は、いずれも正の整数で、百万を超えることはありません。
ひとつの入力に含まれる 三角形-点 の組は 10以下です。
いずれの三角形も、ゼロより大きな面積を持ちます。
不正な入力に対処する必要はありません。
Rubyで解答しています。
#!/usr/bin/ruby
# 入力値のパース
# [a,b,c,p]を返す
def parse(param)
ret = []
md = param.match(/\(([0-9]+,[0-9]+)\)\(([0-9]+,[0-9]+)\)\(([0-9]+,[0-9]+)\)\/\(([0-9]+,[0-9]+)\)/)
for i in 1..4
v = md[i].split(",").map{|a| a.to_i}
ret << v
end
return ret
end
# ベクトルの差
def sub_vector(x, y)
return [x[0]-y[0], x[1]-y[1]]
end
# 外積
def cross(x, y)
return (x[0] * y[1]) - (x[1] * y[0])
end
# 頂点にある場合以外のチェック
# 引数はそれぞれ外積の結果
# 外積のいずれかが0の場合は辺上にある
# 全部が同じ方向を向いているなら内側にある
# どれかが違う方向なら外側にある
def check(c1, c2, c3)
if (c1 == 0) || (c2 == 0) || (c3 == 0) then
is_b = 1
for c in [c1, c2, c3]
if c == 0 then next
elsif c > 0 then is_b *= 1
else is_b *= -1
end
end
if is_b == 1 then return "B"
else return "D"
end
elsif (c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0) then return "A"
else return "D"
end
end
# 問題を解く
# 参考：http://www.sousakuba.com/Programming/gs_hittest_point_triangle.html
def solve(line)
ret = []
inputs = line.split
for param in inputs
a,b,c,q = parse(param)
# 頂点にあるかチェック
if (a == q) || (b == q) || (c == q) then
ret << "C"
next
end
ab = sub_vector(b, a)
bc = sub_vector(c, b)
ca = sub_vector(a, c)
bq = sub_vector(q, b)
cq = sub_vector(q, c)
aq = sub_vector(q, c)
c1 = cross(ab, bq)
c2 = cross(bc, cq)
c3 = cross(ca, aq)
ret << check(c1, c2, c3)
end
return ret.join("")
end
# main
while line = gets
line.strip!
if line.empty? then next end
puts solve(line)
end
ここのところ難しい問題が続いたのでちょっとホッとしました。
とはいえ、この問題が簡単かというとそうではありません。たぶん高校レベルの数学では苦労します（私の高校時代にはベクトルの外積は高校では習わなかったと記憶しています。）。ただ、調べれば必ずやり方がわかる問題ではあります。
この問題を読んだ時、必ず一般的なやり方があるだろうと思いました。CGとかゲームである範囲内に点があるかどうかを判断する方法だからです。で、調べたらやはり見つかりました（実際に参考にしたサイトのURLはコメントに書いてあります。
そのサイトによると三角形ABCに対して点Pが内側にあるかどうかはベクトルABとBP、BCとCP、CAとAPそれぞれの外積が同じ方向を向く（±符号が同じになる）ということでした。参考のサイトでは線上にある場合は外側にあるとして扱っていたと思います（内側だったかもしれません）が、多分0になるだろうと思って確認したらその通りでした。
これだけのことがわかれば後はその通りにコーディングするだけです。
入力値の1グループ（(1,1)(10,1)(1,10)/(2,2)）をパースして三角形の頂点と点Pの座標を配列として返します。正規表現で簡単に取り出せるので正規表現で数字だけを抜き出して数値に変換して返します。
「ベクトルの差」コメントしていますが、座標からベクトルを求めます。
特に説明は必要ないでしょう。
ベクトルの外積を求めて返します。
これもやっていることは一目瞭然なので説明は不要でしょう。
点と三角形の位置をチェックします。
点Pが頂点に一致している場合は先にチェック済みなのでここではチェックしません。
入力値はベクトルABとBP、BCとCP、CAとAPそれぞれの外積です。
まず、いずれかが0の場合、点Pは辺上にあるか、辺の延長上にあります（34〜45行目）（この問題の引っ掛けのパターンになっています。私は引っかかりました）。辺上にある場合、0以外の2つのベクトルは同じ±符号になりますが、辺の延長上にある場合は符号が異なりますのでこれをチェックします（35〜45行目）。
次に、全てのベクトルの符号が同じ場合は点Pは三角形の内側にあります（46行目）。
それ以外の場合、点Pは三角形の外側にあります（47行目）。
問題を解きます。
まず、入力値を"/"で分割してparse()にかけ、1組ごとに座標を取得します（57行目）。点Pが変数qになっていますが、これはRubyにp()という関数があって名前がかぶるのでqにしています。
まず、点Pが頂点に一致するかをチェックしてしまいます（60〜63行目）。
頂点に一致した場合は結果をretに追加して次の組に移ります。
ベクトルAB、BC、CAを求めます（56〜67行目）。同様にベクトルBP、CP、APを求めます（69〜71行目）。それからベクトルABとBP、BCとCP、CAとAPの外積を求めます（73〜75行目）。
そして、check()に外積で求めたベクトルを渡して結果を取得しretに追加します。
最終的に結果の配列を標準出力のフォーマット文字列にして返します。
久しぶりにあっさりとできる問題でホッとしました。
ただし、外積を使う方法を調べず自力でやろうとしたら非常に苦労したと思います。
なので、この問題に関して一番のファインプレーはCGなどを扱う場合の基本的なロジックだから効率の良い、確立した方法があるだろうと考えて、自分では考えず調べたことになります。