凸包を求めるPython3用関数を示す。

座標(x,y) は complex型データのリストで与えられるものとする。Python3では、複素数を扱うためのcomplex型がサポートされていて、以下ではreal部分をx座標、imag部分をy座標としている。

例えば、4点(0,0), (1,0), (1,1), (0,1)の座標に対応して、Python3は以下のようなリスとで表現する

a = [0, 1, 1+1j, 1j]

凸包関数のリターン値として、凸包を構成する座標のリストを反時計回りで得られる。リストの長さは座標数に対応する。

# AOJ 0068 Enclose Pins with a Rubber Band
# Python3 2018.6.22 bal4u

def cross(a, b):
	return a.real*b.imag - a.imag*b.real
	
# 凸包 入力: 座標リスト リターン:凸包を構成する座標リスト
def convex_hull(p):
	pp = sorted(p, key=lambda x:(x.imag,x.real))  # y座標を優先して昇順、同じならx座標で昇順
	n = len(pp)
	ans, j = [0]*(n+1), 0
	for i in range(n):
		while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	k = j
	for i in range(n-2, -1, -1):
		while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	return ans[0:j-1]
	
while 1:
	n = int(input())
	if n == 0: break
	p = []
	for i in range(n):
		x, y = list(map(float, input().split(',')))
		p.append(complex(x, y))
	print(n - len(convex_hull(p)))

問題文 AOJ-068 を解くためにC言語プログラムから移植したもの。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Post Navigation