プロジェクトオイラー 問１０２

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１０２「三角形の包含」
3つの異なる点が -1000 ≦ x, y ≦ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.

以下の2つの三角形を考える.

A(-340,495), B(-153,-910), C(835,-947) 
X(-175,41), Y(-421,-714), Z(574,-645)
三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.

27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.

注: ファイル中の最初の二つは三角形ABC, XYZである.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(fn):
	c = 0
	p = open(fn)
	for s in p.readlines():
		t, L, M = s.split(","), [], []
		for i in xrange(0, len(t), 2): L.append((int(t[i]), int(t[i+1]))) 
		L.append(L[0])
		for i in xrange(len(t)//2):
			a, b = L[i], (L[i+1][0]-L[i][0], L[i+1][1]-L[i][1])
			M.append(a[0]*b[1] - a[1]*b[0])
		if abs(sum(M))==sum([abs(u) for u in M]): c += 1
	p.close()
	p = None
	return c

s = "p102_triangles.txt"
t = os.path.join(os.path.dirname(__file__), s)
print f(t)

原点が三角形の各辺の左右同じ側にあるかという位置関係で判定します。
ベクトルの外積を利用します。

対象となる点（当問題では原点）が三角形の内部にあれば、
その点は三角形を一周して常に同じ側にあることになります。
つまり、対象となる点（当問題では原点）から各頂点へのベクトルと、
その頂点から次の頂点へのベクトルの外積の符号がすべて同じになります。
なお、平面上の話なので、外積はベクトルにならずスカラー量です。

aベクトル：原点から三角形のi番目の頂点へのベクトル
bベクトル：i番目の点からi+1番目の点へのベクトル
として、
aベクトルとbベクトルの外積の符号が、
正ならばaベクトルが右側、つまり原点はbベクトルの左側で、
負ならばaベクトルが左側、つまり原点はbベクトルの右側です。
３つの外積がすべて正ならば原点を右回りに一周し、
３つの外積がすべて負ならば原点を左回りに一周することになります。

外積の公式は以下のとおりです。
aベクトル=(A_x, A_y)、bベクトル=(B_x, B_y)とすると、
a×b = A_x*B_y - A_y*B_x

以上を実装しました。

１．関数f(fn)
・入力ファイルのフルパスを受け取り、問題にある内部に原点を含む三角形の数を返します。
・ループ変数sは、入力ファイルの１行分で、６つの数字のcsv文字列です。
・変数tは、６つの数字（まだ文字型）を持つリストです。
・一周して計算する都合上、最初の座標を最後にもう一度追加し
座標を４つ分にしてから外積計算を３回行います。
リストLは、平面座標値（タプル型）を最初３つ持ち、最初の１つを末尾に追加して
計４つの座標値を持ちます。
・変数a,bはそれぞれ上記の説明にあるaベクトルとbベクトルです。
・リストMには外積値をためていきます。
・外積の符号一致判定は、外積値の和の絶対値＝外積値の絶対値の和かどうかで行います。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
228