AOJのこの問題を解くのに次のようなコードを書いた。
import sys
import math
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
class Vector:
def __init__(self, p1, p2):
self.vx = p2.x - p1.x
self.vy = p2.y - p1.y
def length(self):
return math.sqrt(self.vx ** 2.0 + self.vy ** 2.0)
def degree(self, other):
theta = math.acos((self.vx * other.vx + self.vy * other.vy)/(self.length() * other.length()))
return theta
def show(self):
return "Vector(%f, %f)" % (self.vx, self.vy)
def solv(points):
p0 = points[0]
for p in points[1:]:
if p.y < p0.y:
p0 = p
v1 = Vector(Point(0.0, 0.0), Point(1.0, 0.0))
p1 = p0
t = [p1]
while True:
min_deg = math.pi
next_p = None
next_v = None
points2 = list(points)
points2.remove(p1)
for p2 in points2:
v2 = Vector(p1, p2)
deg = v1.degree(v2)
if deg < min_deg:
min_deg = deg
next_p = p2
next_v = v2
if next_p == p0:
break
p1 = next_p
t.append(p1)
v1 = next_v
return len(points) - len(t)
while True:
n = int(sys.stdin.readline())
if n == 0:
break
points = []
for i in range(n):
x, y = map(float, sys.stdin.readline().split(','))
points.append(Point(x, y))
print solv(points)
複数の点が与えられて、凸包の中にある点の数を出力する問題で、ググってあちこちのページを参考にしながら書いたので、エレガントじゃないとかそういうことは置いといてたぶんあってる。 簡単に説明しておくと、一番下の点を出発点として左回りに凸包に含まれる点を探索している。この時、すでに凸包に含まれるのが明らかになっている最後の2点を結ぶベクトルと、最後の1点とその他の点を結ぶベクトルのなす角度をそれぞれ求めて、角度が最も小さい点を次の点としている。で、最初の点に戻ってくるまでループしてるわけだ。 さて、これにサンプルのデータを与えて実行するとタイトルのようなエラーが出る。
^o^ > python problem0-0068.py < input0-0068.txt
0
Traceback (most recent call last):
File "problem0-0068.py", line 70, in
print solv(points)
File "problem0-0068.py", line 48, in solv
deg = v1.degree(v2)
File "problem0-0068.py", line 25, in degree
theta = math.acos((self.vx * other.vx + self.vy * other.vy)/(self.length() *
other.length()))
ValueError: math domain error
math.acos()のところでエラーになっている。ここには載せないけどサンプルの入力データには2つのデータセットがあって、1つ目のデータセットに対する出力は正常にされている。最初の0がそうだ。これはサンプルの回答ともあっている。だけど2つ目のデータセットではエラーが発生する。
詳しく調べてみると、math.acos()の引数が-1.0の時にエラーになっているんだけど、引数が-1.0になるのは1度じゃなく何度もあって、エラーが発生しないときもある（というか発生しないほうが多い）。実際1つ目のデータセットには正解を返してるわけだし。
ググってみてもこの math domain error というのがどういうエラーなのかよくわからない。
いくら悩んでもわからないので、ダメもとでAOJに提出したら、あっさりとAcceptedになってしまった。
わけがわからないよ。