Problem p03428 (python)

Fixed submission:
import math
N = int(input())
ps = []
for i in range(N):
  x, y = map(int, input().split())
  ps.append((x, y, i))
ps.sort()

# i -> j のベクトル
def vec(pi, pj):
  return (pj[0] - pi[0], pj[1] - pi[1])
# i -> j 向きの外積
def det(vi, vj):
  return vi[0] * vj[1] - vi[1] * vj[0]

# 凸包を求める
cvx = []
for i in list(range(N)) + list(range(N-1))[::-1]:
  while len(cvx) >= 2 and det(vec(ps[cvx[-2]], ps[cvx[-1]]), vec(ps[cvx[-1]], ps
[i])) < 0:
    cvx.pop()
  cvx.append(i)

# 凸包の各頂点について、頂点から出る2辺のなす角を計算
ans = {}
pi = None
for i in cvx:
  x, y, j = ps[i]
  if pi is not None:
    px, py, pj = ps[pi]
    slope = math.atan2(y-py, x-px)
    if j not in ans: ans[j] = [0, 0]
    if pj not in ans: ans[pj] = [0, 0]
    ans[j][0] = slope
    ans[pj][1] = slope
  pi = i

for i in range(N):
  if i not in ans:
    print(0)
    continue
  v1, v2 = ans[i]
  if v2 < v1:
    v2 += 2*math.pi
  print(round((v2-v1) / (2*math.pi), 8))

Buggy submission (verdict: Runtime Error):
import math
N = int(input())
ps = []
minx = float('inf')
miny = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x < minx or (x == minx and y < miny):
    minx = x
    miny = y
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  b = (1/a**2)
  x = math.sqrt(1/(1+b))
  y = math.sqrt(b/(1+b))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  xnow = ps[now][0]
  ynow = ps[now][1]
  for j in range(N):
    if j == now or j != first and j in divvecs: continue
    xj = ps[j][0]
    yj = ps[j][1]
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(xj, yj, xnow, ynow, ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(xnow, ynow, xj, yj)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      divvecs[now].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))

Buggy submission (verdict: Runtime Error):
import math
N = int(input())
ps = []
minx = float('inf')
miny = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x <= minx and y < miny:
    minx = x
    miny = y
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  b = (1/a**2)
  x = math.sqrt(1/(1+b))
  y = math.sqrt(b/(1+b))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  for j in range(N):
    if j == now or j != first and j in divvecs: continue
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(ps[j][0], ps[j][1], ps[now][0], ps[now][1], ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(ps[now][0], ps[now][1], ps[j][0], ps[j][1])
      divvecs[now].append(divv)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))

Buggy submission (verdict: Runtime Error):
import math
N = int(input())
ps = []
minx = float('inf')
miny = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x <= minx and y < miny:
    minx = x
    miny = y
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  b = (1/a**2)
  x = math.sqrt(1/(1+b))
  y = math.sqrt(b/(1+b))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  for j in range(N):
    if j != first and j in divvecs: continue
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(ps[j][0], ps[j][1], ps[now][0], ps[now][1], ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(ps[now][0], ps[now][1], ps[j][0], ps[j][1])
      divvecs[now].append(divv)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))

Buggy submission (verdict: Runtime Error):
import math
N = int(input())
ps = []
minx = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x < minx:
    minx = x
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  a = - (1/a) # 垂直
  x = math.sqrt(1/(1+a**2))
  y = math.sqrt((a**2)/(1+a**2))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = 0
now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  for j in range(N):
    if j == now: continue
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(ps[j][0], ps[j][1], ps[now][0], ps[now][1], ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(ps[now][0], ps[now][1], ps[j][0], ps[j][1])
      divvecs[now].append(divv)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))