Problem:


Score : 600 points

Problem Statement

There are N holes in a two-dimensional plane. The coordinates of the i-th hole are (x_i,y_i).

Let R=10^{10^{10^{10}}}. Ringo performs the following operation:

Randomly choose a point from the interior of a circle of radius R centered at the origin, and put Snuke there. Snuke will move to the hole with the smallest Euclidean distance from the point, and fall into that hole. If there are multiple such holes, the hole with the smallest index will be chosen.

For every i (1 \leq i \leq N), find the probability that Snuke falls into the i-th hole.

Here, the operation of randomly choosing a point from the interior of a circle of radius R is defined as follows:

Pick two real numbers x and y independently according to uniform distribution on [-R,R].

If x^2+y^2\leq R^2, the point (x,y) is chosen. Otherwise, repeat picking the real numbers x,y until the condition is met.

Constraints

2 \leq N \leq 100

|x_i|,|y_i| \leq 10^6(1\leq i\leq N)

All given points are pairwise distinct.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print N real numbers. The i-th real number must represent the probability that Snuke falls into the i-th hole.

The output will be judged correct when, for all output values, the absolute or relative error is at most 10^{-5}.

Sample Input 1

2
0 0
1 1

Sample Output 1

0.5
0.5

If Ringo put Snuke in the region x+y\leq 1, Snuke will fall into the first hole. The probability of this happening is very close to 0.5.
Otherwise, Snuke will fall into the second hole, the probability of which happening is also very close to 0.5.

Sample Input 2

5
0 0
2 8
4 5
2 6
3 10

Sample Output 2

0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727



Sample input:
2
0 0
1 1


Sample output:
0.5
0.5

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
import numpy as np


def solve(n, pts):
    ans = [0] * n

    div = 200000
    a = np.linspace(0, 2 * np.pi, div)
    b = np.dot(pts, [np.sin(a), np.cos(a)])
    c = np.argmax(b, axis=0)
    for i, v in zip(*np.unique(c, return_counts=True)):
        ans[i] = v / div
    return ans


n = int(input())
pts = [list(map(int, input().split())) for _ in range(n)]
print('\n'.join(map(str, solve(n, pts))))

Submission status: Runtime Error

Solution code:
import numpy as np


def solve(n, pts):
    ans = [0] * n

    div = 1000000
    a = np.linspace(0, 2 * np.pi, div)
    b = np.dot(pts, [np.sin(a), np.cos(a)])
    c = np.argmax(b, axis=0)
    for i, v in zip(*np.unique(c, return_counts=True)):
        ans[i] = v / div
    return ans


n = int(input())
pts = [list(map(int, input().split())) for _ in range(n)]
print('\n'.join(map(str, solve(n, pts))))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.spatial import ConvexHull


def solve(n, pts):
    if n == 2:
        return [0.5, 0.5]

    hull = ConvexHull(pts)
    ps = np.array(list(map(pts.__getitem__, hull.vertices)))
    vs = ps - np.roll(ps, 1, axis=0)

    vt = vs.T
    vt[0] *= -1
    arcs = np.arctan2(*vt)
    arcs = np.append(arcs, arcs[0])
    da = np.diff(arcs) / (2 * np.pi) % 1
    
    ans = [0] * n
    for i, a in zip(hull.vertices, da):
        ans[i] = a

    return ans


n = int(input())
pts = np.array([list(map(int, input().split())) for _ in range(n)])
print('\n'.join(map(str, solve(n, pts))), end='')

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
from math import sin, cos, pi
n = int(input())
xx = []
yy = []
for i in range(n):
  x, y = map(int, input().split())
  xx.append(x)
  yy.append(y)
D = 250000
ii = list(range(n))
prob = [0.0] * n
for d in range(D):
  s = sin(2 * pi * d / D)
  c = cos(2 * pi * d / D)
  i = max(ii, lambda i: x[i]*s + y[i]*c)
  prob[i] += 1 / D
for p in prob:
  print(p)

Submission status: Runtime Error

Solution code:
from math import acos, hypot, pi


class Point:
    def __init__(self, i, x, y):
        self.i = i
        self.x = int(x)
        self.y = int(y)


class Line:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
        self.d2 = (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2
        if p1.x == p2.x:
            self.a = 1
            self.b = 0
            self.c = -p1.x
        else:
            self.a = p2.y - p1.y
            self.b = p1.x - p2.x
            self.c = -p1.y * self.b - p1.x * self.a

    def dist(self, p):
        f = self.a * p.x + self.b * p.y + self.c
        if f == 0:
            d12 = (self.p1.x - p.x) ** 2 + (self.p1.y - p.y) ** 2
            d22 = (self.p2.x - p.x) ** 2 + (self.p2.y - p.y) ** 2
            if self.d2 < max(d12, d22):
                return None
            return 0
        if f < 0:
            return -1
        else:
            return 1

    def kaku(self, other):
        x = self.a * other.a + self.b * other.b
        x /= hypot(self.a, self.b) * hypot(other.a, other.b)
        return pi - acos(x)


def make_p(n, pp):
    pids = {p.i: [] for p in pp}
    for i in range(n):
        if len(pids[i]) == 2:
            continue
        p1 = pp[i]
        for j in pids:
            if i == j or len(pids[j]) == 2:
                continue
            p2 = pp[j]
            line = Line(p1, p2)
            ptype = {0: 0, 1: 0, -1: 0, None: 0}
            for k in pids:
                if k == i or k == j:
                    continue
                ptype[line.dist(pp[k])] += 1
            if ptype[None]:
                del pids[j]
            if ptype[1] == 0 or ptype[-1] == 0:
                pids[i].append(j)
                pids[j].append(i)
    return pids


def main():
    n = int(input())
    if n == 2:
        print(0.5)
        print(0.5)
        return
    pp = []
    for i in range(n):
        p = Point(i, *input().split())
        pp.append(p)
    pids = make_p(n, pp)
    prob = [0.0] * n
    for i, nei in pids.items():
        if len(nei) == 2:
            l1 = Line(pp[i], pp[nei[0]])
            l2 = Line(pp[i], pp[nei[1]])
            kaku = l1.kaku(l2)
            prob[i] += kaku / (2 * pi)
    for p in prob:
        print(p)


if __name__ == '__main__':
    main()