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: Accepted

Solution code:
import math


class ConvexHull:
    """凸包に関する各種性質を求める"""
    def __init__(self, ps):
        self.n = len(ps)
        self.ps = sorted(ps)
        self.qs = []

        # 下側凸包の構築
        for p in self.ps:
            while len(self.qs) > 1 and self._ccw(self.qs[-2], self.qs[-1], p) < 0:
               self.qs.pop()
            self.qs.append(p)
        t = len(self.qs)

        # 上側凸包の構築
        for i in range(self.n - 2, -1, -1):
            p = self.ps[i]
            while len(self.qs) > 1 and self._ccw(self.qs[-2], self.qs[-1], p) < 0:
               self.qs.pop()
            self.qs.append(p)

    def _ccw(self, p1, p2, p3):
        """p1 -> p2 -> p3と頂点を移動したときの回転方向を返す。
        反時計回り -> +1、時計回り -> -1、0°もしくは180°回る -> 0
        """
        p2 = [p2[i] - p1[i] for i in range(2)]
        p3 = [p3[i] - p1[i] for i in range(2)]
        if p2[0] * p3[1] == p2[1] * p3[0]:
            return 0
        if p2[0] * p3[1] - p2[1] * p3[0] > 0:
            return +1
        else:
            return -1

    def get_ps(self):
        """凸包の頂点組を反時計回り順で求める（GrahamScan）。"""
        return self.qs


def get_theta(o, a, b):
    a = [a[i] - o[i] for i in range(2)]
    b = [b[i] - o[i] for i in range(2)]
    len_a = (a[0] ** 2 + a[1] ** 2) ** 0.5
    len_b = (b[0] ** 2 + b[1] ** 2) ** 0.5
    ab = a[0] * b[0] + a[1] * b[1]
    return 180 - math.degrees(math.acos(ab / len_a / len_b))


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

to_ind = {}
for i in range(n):
    to_ind[tuple(info[i])] = i

gs = ConvexHull(info)
ps = gs.get_ps()[:-1]
m = len(ps)

ans = [0.0] * n 
for i in range(m):
    ind = to_ind[tuple(ps[i])]
    ans[ind] = get_theta(ps[i], ps[(i - 1) % m], ps[(i + 1) % m]) / 360

for res in ans:
    print(res)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00




n = int(input())
xy = []

for i in range(n):
    xy.append(list(map(int, input().split())))
    xy[-1].append(i)
    
origin = list(xy)
xy.sort(key = lambda x : -x[1])
xy.sort(key = lambda x : x[0])
#print(xy)

down = [0]

while(True):
    now = down[-1]
    nowxy = xy[down[-1]]
    #print(now,nowxy)
    if(now==n-1):
        break
    shouldBreak = 0
    for j in range(now+1,n):
        if(nowxy[0] == xy[j][0]):
            down.append(j)
            shouldBreak=1
            break
    if(shouldBreak):
        continue
    gradmin = 10**18
    nxt = -1
    for j in range(now+1,n):
        grad = (xy[j][1]-nowxy[1])/(xy[j][0]-nowxy[0])
        #print(grad)
        if(gradmin > grad):
            gradmin = grad
            nxt = j
            
    down.append(nxt)
#print(down)
down = [xy[i][2] for i in down]
down = down[0:len(down)-1]
#print(down)

xy.sort(key = lambda x : x[1])
xy.sort(key = lambda x : -x[0])
#print(xy)

up = [0]
    
while(True):
    now = up[-1]
    nowxy = xy[up[-1]]
    #print(now,nowxy)
    if(now==n-1):
        break
    
    shouldBreak = 0
    for j in range(now+1,n):
        if(nowxy[0] == xy[j][0]):
            up.append(j)
            #print(j)
            shouldBreak=1
            break
    if(shouldBreak):
        continue
    gradmin = 10**18
    nxt = -1
    for j in range(now+1,n):
        grad = (xy[j][1]-nowxy[1])/(xy[j][0]-nowxy[0])
        if(gradmin > grad):
            #print("g",j,grad)
            gradmin = grad
            nxt = j
            
    up.append(nxt)
    #print(up)
#print(up)
up = [xy[i][2] for i in up]
up = up[:len(up)-1]
#print(up)
seq = list(down)
for i in up:
    seq.append(i)

#print(seq)

ans = [0.0 for i in range(n)]

def u2(a):
    return math.sqrt(a[0]*a[0]+a[1]*a[1])
def dot(a,b):
    return a[0]*b[0]+a[1]*b[1]

m = len(seq)
for i in range(len(seq)):
    num1,num2,num3 = seq[(i-1)%m],seq[i],seq[(i+1)%m]
    p1,p2,p3 = origin[num1],origin[num2], origin[num3]
    left = [p1[0]-p2[0],p1[1]-p2[1]]
    right = [p3[0]-p2[0],p3[1]-p2[1]]
    cos = dot(left,right)/u2(left)/u2(right)
    #print(cos,left,right)
    deg = math.pi - math.acos(cos)
    ans[num2] = deg/(2.0*math.pi)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
n = int(input())
ipt = [list(map(int,input().split())) for i in range(n)]
xy = sorted(ipt)
convh1 = [xy[0],xy[1]]
def slope(xy1,xy2,const = 1):
  x1,y1 = xy1
  x2,y2 = xy2
  dx,dy = x2-x1,y2-y1
  if dx == 0:
    return 10**18*(y2-y1)*const//abs(y2-y1)
  else:
    return dy/dx
def convex(xy1,xy2,xy3,const = 1):
  x1,y1 = xy1
  x2,y2 = xy2
  x3,y3 = xy3
  if slope([x1,y1],[x2,y2],const) < slope([x2,y2],[x3,y3],const):
    return True
  return False
for i in range(2,n):
  x,y = xy[i]
  while len(convh1) >= 2 and not convex(convh1[-2],convh1[-1],[x,y]):
    convh1.pop()
  convh1.append(xy[i])
convh2 = [xy[-1],xy[-2]]
for i in range(n-2)[::-1]:
  x,y = xy[i]
  while len(convh2) >= 2 and not convex(convh2[-2],convh2[-1],[x,y],-1):
    convh2.pop()
  convh2.append(xy[i])
convh = convh1+convh2[1:-1]
prob = [0 for i in convh]
dc = defaultdict(int)
for i,xy in enumerate(convh):
  x,y = xy
  px,py = convh[i-1]
  nx,ny = convh[(i+1)%len(convh)]
  px -= x
  py -= y
  nx -= x
  ny -= y
  rad = math.atan2(ny,nx)-math.atan2(py,px)
  dc[(x,y)] = (math.pi-min(abs(rad),2*math.pi-abs(rad)))/(2*math.pi)
for x,y in ipt:
  print(dc[(x,y)])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]

    def det(x, y, z):
        a = [x[0]-y[0], x[1]-y[1]]
        b = [z[0]-x[0], z[1]-x[1]]
        return a[0]*b[1]-a[1]*b[0]

    def convex_hull(ab):
        q, k = [], 0
        xy = sorted(ab)  # ここをいじることで初期位置を変えられる。
        for i in range(n):
            while k > 1 and det(q[k-1], q[k-2], xy[i]) <= 0:
                k -= 1
                q.pop()
            q.append(xy[i])
            k += 1
        t = k
        for i in range(n-2, -1, -1):
            while k > t and det(q[k-1], q[k-2], xy[i]) <= 0:
                k -= 1
                q.pop()
            q.append(xy[i])
            k += 1
        return q[:k-1]

    ans = convex_hull(ab)
    l = len(ans)
    d = dict()
    from math import acos
    from math import pi
    if l == 2:
        for a, b in ans:
            d[(a, b)] = 0.5
    else:
        b = 0
        ans += ans
        for i in range(l):
            a1 = ans[i][0]-ans[i-1][0]
            b1 = ans[i][1]-ans[i-1][1]
            a2 = ans[i+1][0]-ans[i][0]
            b2 = ans[i+1][1]-ans[i][1]
            a = acos((a1*a2+b1*b2)/((a1**2+b1**2)*(a2**2+b2**2))**0.5)
            d[tuple(ans[i])] = a/2/pi
    for a, b in ab:
        if (a, b) in d:
            print(d[(a, b)])
        else:
            print(0)


main()

Submission status: Accepted

Solution code:
import math

N = int(input())
xys = [tuple(map(int, input().split())) for _ in range(N)]

if N == 2:
    print(0.5)
    print(0.5)
    exit()

outside = [min(range(N), key = lambda i: xys[i])]

go_back_to_while = False
while outside:
    i = outside[-1]
    x1, y1 = xys[i]
    for j in range(N):
        if j in outside:
            continue
        x2, y2 = xys[j]
        sign = 0
        for k, (x3, y3) in enumerate(xys):
            if k == i or k == j:
                continue
            tmp = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
            if tmp == 0:
                if x1 < x3 < x2 or x1 > x3 > x2 or y1 < y3 < y2 or y1 > y3 > y2:
                    if k in outside:
                        outside.remove(k)
                        outside.append(j)
                        go_back_to_while = True
                        break
                elif x1 < x2 < x3 or x1 > x2 > x3 or y1 < y2 < y3 or y1 > y2 > y3:
                    break
                else:
                    outside.pop() #remove i
                    go_back_to_while = True
                    break
            elif tmp > 0:
                if sign == 0:
                    sign = +1
                elif sign == -1:
                    break
                else:
                    continue
            else:
                if sign == 0:
                    sign = -1
                elif sign == +1:
                    break
                else:
                    continue
        else:
            outside.append(j)
            break
        if go_back_to_while:
            go_back_to_while = False
            break
    else: #when not found appropriate j
        break #get out of while True


ans = [0.0] * N

for i in range(-1, len(outside) - 1):
    x1, y1 = xys[outside[i-1]]
    x2, y2 = xys[outside[i]]
    x3, y3 = xys[outside[i+1]]
    v1x, v1y = x2 - x1, y2 - y1
    v2x, v2y = x3 - x2, y3 - y2
    dot = v1x * v2x + v1y * v2y
    len1 = (v1x ** 2 + v1y ** 2)
    len2 = (v2x ** 2 + v2y ** 2)
    ans[outside[i]] = math.acos( max(-1.0, min(1.0, dot / math.sqrt(len1 * len2))) ) / (2 * math.pi)

for a in ans:
    print('{:.20f}'.format(a))

Submission status: Accepted

Solution code:
import math

def norm(p, q): # normal vector: (p -> q) * -1j
    return (q[1] - p[1], p[0] - q[0])

def magnitude(a):
    return (a[0]**2 + a[1]**2)**.5

def dot(p, q):
    return p[0]*q[0] + p[1]*q[1]

def angle(p, q):
    return math.acos(dot(p, q) / (magnitude(p) * magnitude(q)))

def cross(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def convex_hull(ps):
    ps = sorted(ps)
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs) > 1 and cross(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n - 2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    return qs

n = int(input())
s = [tuple(map(int, input().split())) for _ in range(n)]
ch = convex_hull(s)
ch.pop()
m = len(ch)
d = dict()
for i in range(m):
  u = angle(norm(ch[i-1], ch[i]), norm(ch[i], ch[(i+1)%m]))
  d[ch[i]] = u / 2 / math.pi
for t in s:
  print(0.0 if t not in d else d[t])

Submission status: Accepted

Solution code:
# 写経AC
import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.qhull import QhullError
from scipy.spatial.distance import cosine

def solve(n, pts):
    ans = np.zeros(n)

    try:
        # 凸包
        hull = ConvexHull(pts)
    except QhullError: # 与えられた点が一直線に並ぶ場合
        # 左端の穴
        ans[pts.index(min(pts))] = 0.5
        # 右端の穴
        ans[pts.index(max(pts))] = 0.5
        return ans

    # 凸包の頂点数
    L = hull.vertices.shape[0]

    for i,v in enumerate(hull.vertices):
        # 時計回り
        prv = hull.vertices[(i - 1) % L]
        # 反時計回り
        nxt = hull.vertices[(i + 1) % L]

        # arccos(コサイン距離) -> 角度
        deg = np.arccos(1 - cosine(hull.points[prv] - hull.points[v], hull.points[nxt] - hull.points[v]))

        ans[v] = (np.pi - deg) / (2 * np.pi)

    return ans

def main():
    N = int(input())
    XY = [[int(i) for i in input().split()] for _ in range(N)]
    print(*solve(N, XY), sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import atan2, pi

N, *XY = map(int, open(0).read().split())
XY = list(zip(*[iter(XY)] * 2))

for i, (x, y) in enumerate(XY):
    D = sorted(atan2(X - x, Y - y) for j, (X, Y) in enumerate(XY) if j != i)
    D.append(D[0] + 2 * pi)

    print(min((b - a - pi for a, b in zip(D, D[1:]) if b - a > pi), default=0) / (2 * pi))

Submission status: Accepted

Solution code:
from math import atan2, pi

N, *XY = map(int, open(0).read().split())
XY = list(zip(*[iter(XY)] * 2))

for i, (x, y) in enumerate(XY):
    D = sorted(atan2(X - x, Y - y) for j, (X, Y) in enumerate(XY) if j != i)
    D.append(D[0] + 2 * pi)

    ans = 0
    for a, b in zip(D, D[1:]):
        if b - a >= pi:
            ans = (b - a) - pi
            break

    print(ans / (2 * pi))

Submission status: Accepted

Solution code:
from math import atan2, pi

N, *XY = map(int, open(0).read().split())
XY = list(zip(*[iter(XY)] * 2))

for i, (x, y) in enumerate(XY):
    D = sorted(atan2(X - x, Y - y) for j, (X, Y) in enumerate(XY) if j != i)
    D.append(D[0] + 2 * pi)

    ans = 0
    for a, b in zip(D, D[1:]):
        if b - a >= pi:
            ans = (b - a) - pi

    print(ans / (2 * pi))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.qhull import QhullError
from numpy.linalg import norm


def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append([x, y])

    ans = np.zeros(N)
    try:
        hull = ConvexHull(points)
    except QhullError:
        ans[points.index(min(points))] = ans[points.index(max(points))] = 0.5
        print(*ans, sep='\n')
        return

    v = hull.vertices
    prv_v, nxt_v = np.roll(v, -1), np.roll(v, 1)
    diff_prev = hull.points[prv_v]-hull.points[v]
    diff_next = hull.points[nxt_v]-hull.points[v]
    deg = np.arccos(np.einsum("ij, ij->i", diff_prev, diff_next) /
                    norm(diff_prev, axis=1) / norm(diff_next, axis=1))
    ans[v] = (np.pi - deg) / (2 * np.pi)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from math import atan2, pi
readline = sys.stdin.readline
def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

Prob = Counter()
N = int(readline())
Points = [tuple(map(int, readline().split())) for _ in range(N)]
Pointsorig = Points[:]
Points.sort()

lower = []
for p in Points:
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
        lower.pop()
    lower.append(p)
upper = []
for p in Points[::-1]:
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
        upper.pop()
    upper.append(p)

convexhull = lower[1:-1] + upper
M = len(convexhull)
convexhull += [convexhull[0]]
convexhull += [convexhull[1]]

for i in range(1, M+1):
    pn = convexhull[i]
    A = (convexhull[i-1][1] - pn[1] , convexhull[i-1][0] - pn[0])
    B = (convexhull[i+1][1] - pn[1] , convexhull[i+1][0] - pn[0])
    theta = abs(pi - abs(atan2(*A) - atan2(*B)))
    Prob[pn] = theta/(2*pi)
Ans = [0]*N
for i in range(N):
    Ans[i] = Prob[Pointsorig[i]]
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

Theta = [[0, 0] for _ in range(N)]

line = True
for i in range(N-1):
    x1, y1 = XY[i]
    for j in range(i+1, N):
        x2, y2 = XY[j]
        for k in range(N):
            x3, y3 = XY[k]
            if (y1-y2)*(x1-x3) != (y1-y3)*(x1-x2):
                line = False
                break
    if line:
        break

if line:
    for i, (x1, y1) in enumerate(XY):
        max_x = True
        min_x = True
        max_y = True
        min_y = True
        for j, (x2, y2) in enumerate(XY):
            if i == j: continue
            if x1 <= x2:
                max_x = False
            if x2 <= x1:
                min_x = False
            if y1 <= y2:
                max_y = False
            if y2 <= y1:
                min_y = False
        if max_x or min_x or max_y or min_y:
            Theta[i][1] = math.pi
else:
    for i in range(N-1):
        x1, y1 = XY[i]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            if x1 == x2:
                all_right = True
                all_left = True
                for k in range(N):
                    if k == i or k == j: continue
                    x3, y3 = XY[k]
                    if x3 > x1:
                        all_left = False
                    elif x3 < x1:
                        all_right = False
                if all_right:
                    if y1 > y2:
                        Theta[i][1] = math.pi
                        Theta[j][0] = math.pi
                    elif y1 < y2:
                        Theta[i][0] = math.pi
                        Theta[j][1] = math.pi
            else:
                all_up = True
                all_down = True
                for k in range(N):
                    if k == i or k == j: continue
                    x3, y3 = XY[k]
                    if (y3-y1)*(x1-x2) < (y1-y2)*(x3-x1):
                        if x1-x2 > 0:
                            all_up = False
                        elif x1-x2 < 0:
                            all_down = False
                    elif (y3-y1)*(x1-x2) > (y1-y2)*(x3-x1):
                        if x1-x2 > 0:
                            all_down = False
                        elif x1-x2 < 0:
                            all_up = False
                if all_down:
                    if x1 < x2:
                        theta = math.atan2(x2-x1, y1-y2)
                        Theta[i][0] = theta
                        Theta[j][1] = theta
                    else:
                        theta = math.atan2(x1-x2, y2-y1)
                        Theta[i][1] = theta
                        Theta[j][0] = theta
                if all_up:
                    if x1 < x2:
                        theta = math.atan2(x1-x2, y2-y1)
                        Theta[i][1] = theta
                        Theta[j][0] = theta
                    else:
                        theta = math.atan2(x2-x1, y1-y2)
                        Theta[i][0] = theta
                        Theta[j][1] = theta

for start, end in Theta:
    delta = end - start
    while delta < 0:
        delta += 2*math.pi
    while delta >= 2*math.pi:
        delta -= 2*math.pi
    print(delta/(2*math.pi))

Submission status: Accepted

Solution code:
import cmath
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def det(a: complex, b: complex):
    # 外積
    return a.real * b.imag - a.imag * b.real


def graham_scan(points):
    """
    凸包
    :param list of complex|np.ndarray points:
    :rtype: list of complex
    """
    if len(points) <= 2:
        return list(points)
    points = np.sort_complex(points)
    # Graham Scan
    sz = 0
    #: :type: list of (complex|None)
    ret = [None] * (N * 2)
    for p in points:
        while sz > 1 and det(ret[sz - 1] - ret[sz - 2], p - ret[sz - 1]) <= 0:
            sz -= 1
        ret[sz] = p
        sz += 1
    floor = sz
    for p in reversed(points[:-1]):
        while sz > floor and det(ret[sz - 1] - ret[sz - 2], p - ret[sz - 1]) <= 0:
            sz -= 1
        ret[sz] = p
        sz += 1
    ret = ret[:sz - 1]
    return ret


N = int(sys.stdin.buffer.readline())
X, Y = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
TAU = math.pi * 2

points = [complex(x, y) for x, y in zip(X, Y)]
pos = {p: i for i, p in enumerate(points)}

# 凸包
points = graham_scan(points)
points = np.array(points, dtype=complex)
assert len(points) >= 2

ans = [0.0] * N

if len(points) == 2:
    ans[pos[points[0]]] = 0.5
    ans[pos[points[1]]] = 0.5
    print(*ans, sep='\n')
    exit()

# 中心からの角度でソート
center = points.mean()
idx = np.angle(points - center).argsort()
points = points[idx]

for i in range(len(points)):
    pr = points[(i + 1) % len(points)]
    p = points[i]
    pl = points[(i - 1) % len(points)]

    # 凸包の内側から、頂点の両隣の辺に垂線をおろしたときの角度
    # pi - 角度
    ans[pos[p]] += (math.pi - (cmath.phase(pl - p) - cmath.phase(pr - p)) % TAU) / TAU

print(*ans, sep='\n')

# from matplotlib import pyplot as plt
#
# points -= center
# theta = [cmath.phase(p) for p in points]
# r = np.array([abs(p) for p in points])
#
# fig = plt.figure()
# ax = fig.add_subplot(111, projection='polar')
# ax.set_ylim([-max(r) * 1.2, max(r) * 1.2])
# ax.scatter(theta, r)
# plt.show()
# print(r)

Submission status: Accepted

Solution code:
from scipy.spatial import ConvexHull as CH
import numpy as np
norm=np.linalg.norm
n,*t=map(int,open(0).read().split())
a=np.reshape(t,(n,2))
try:
	h = CH(a).vertices
except:
	a=a-10**6
	if np.all(a[:,0]==a[0,0]):
		a=np.fliplr(a)
	b=a[:,0]
	M=np.argmax(b)
	m=np.argmin(b)
	for i in range(n):
		print(0.5*(i in (m,M)))
	exit()
l=len(h)
for i in range(n):
	if i in h:
		j=np.where(h==i)[0]
		f,s,t=a[h[j-1]],a[i],a[h[(j+1)%l]]
		print(np.arccos(np.inner(t-s,s-f)/(norm(t-s)*norm(s-f)))[0,0]/(2*np.pi))
	else:
		print(0.)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict


def norm2(vec):
    return math.sqrt(vec[0]**2 + vec[1]**2)


# any 2 points must have different position.
def ConvexHull(point_list):
    pos2idx = {point_list[i]: i for i in range(len(point_list))}
    y_val = defaultdict(list)
    x_list = sorted(list(set([p[0] for p in point_list])))
    for x, y in point_list:
        y_val[x].append(y)

    upper = [(x_list[0], max(y_val[x_list[0]]))]
    lower = [(x_list[0], min(y_val[x_list[0]]))]
    prev = float('inf')
    for xi in x_list[1:]:
        x0, y0 = upper[-1]
        x1, y1 = xi, max(y_val[xi])
        if (y1 - y0) / (x1 - x0) < prev:
            upper.append((x1, y1))
            prev = (y1 - y0) / (x1 - x0)
        else:
            while True:
                x0, y0 = upper[-1]
                if len(upper) == 1:
                    upper.append((x1, y1))
                    break
                x00, y00 = upper[-2]
                if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
                    upper.pop()
                else:
                    prev = (y1 - y0) / (x1 - x0)
                    upper.append((x1, y1))
                    break

    prev = -float('inf')
    for xi in x_list[1:]:
        x0, y0 = lower[-1]
        x1, y1 = xi, min(y_val[xi])
        if (y1 - y0) / (x1 - x0) > prev:
            lower.append((x1, y1))
            prev = (y1 - y0) / (x1 - x0)
        else:
            while True:
                x0, y0 = lower[-1]
                if len(lower) == 1:
                    lower.append((x1, y1))
                    break
                x00, y00 = lower[-2]
                if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
                    lower.pop()
                else:
                    prev = (y1 - y0) / (x1 - x0)
                    lower.append((x1, y1))
                    break

    # return upper, lower
    # return [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]

    upper_idx, lower_idx = [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]
    if upper_idx[-1] == lower_idx[-1]:
        upper_idx.pop()
    CH_idx = upper_idx
    CH_idx.extend(reversed(lower_idx))
    if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
        CH_idx.pop()
    return CH_idx


N = int(input())
point_list = []
for _ in range(N):
    x, y = map(int, input().split())
    point_list.append((x, y))

CH = ConvexHull(point_list)
if len(CH) == 2:
    ans = [0] * N
    ans[CH[0]] = 0.5
    ans[CH[1]] = 0.5
    for i in range(N):
        print(ans[i])
    exit()
ans = [0] * N
for i in range(len(CH)):
    s, t, u = CH[i-1], CH[i], CH[(i+1)%len(CH)]
    x0, y0 = point_list[s]
    x1, y1 = point_list[t]
    x2, y2 = point_list[u]
    vec0 = (y0-y1, x1-x0)
    vec1 = (y1-y2, x2-x1)
    ans[t] = math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)

for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np
from numpy import pi
N = int(input())
X,Y = np.array([input().split() for _ in range(N)],dtype=np.float64).T

# ひとつずつ計算する。垂直二等分線のどっちか側。
# 半平面の共通部分

def solve(i):
    Xother = np.delete(X,i)
    Yother = np.delete(Y,i)
    angle = np.arctan2(Y[i]-Yother,X[i]-Xother) # 半平面の中心線
    # 右半平面に帰着
    angle -= angle[0]
    # -pi,piに含める
    angle[angle<-pi] += 2*pi
    angle[angle>pi] -= 2*pi
    lower = np.zeros_like(angle)
    upper = np.zeros_like(angle)
    case1 = (angle<=0)
    case2 = (angle>=0)
    lower[case1] = -pi/2
    upper[case1] = angle[case1]+pi/2
    lower[case2] = angle[case2]-pi/2
    upper[case2] = pi/2
    
    return max(0,upper.min() - lower.max())/(2*pi)

answer = [solve(i) for i in range(N)]
print(*answer,sep='\n')

Submission status: Accepted

Solution code:
import math
pi=3.141592657589793238462643383279

#quoted from https://atcoder.jp/contests/agc021/submissions/2436528
def cross(C, A, B):
    return (C[0] - A[0])*(C[1] - B[1]) - (C[1] - A[1])*(C[0] - B[0])

def convex_hull(P):
    P.sort()
    Q = []
    for p in P:
        while 1 < len(Q) and cross(Q[-2], Q[-1], p) >= 0:
            Q.pop()
        Q.append(p)
    k = len(Q)
    for p in reversed(P[:-1]):
        while k < len(Q) and cross(Q[-2], Q[-1], p) >= 0:
            Q.pop()
        Q.append(p)
    return Q

n=int(input())
arr=[]
for _ in range(n):
  x,y=map(int,input().split())
  arr.append((x,y))
arr2=convex_hull(arr[:])[:-1]
ans=[0]*n
if n==2:
  print(0.5)
  print(0.5)
else:
  for i in range(n):
    pos=arr[i]
    if pos not in arr2:
      continue
    else:
      idx=arr2.index(pos)
      pos1=arr2[idx-1]
      pos2=arr2[(idx+1)%len(arr2)]
      x1=pos[0]-pos1[0]
      y1=pos[1]-pos1[1]
      x2=pos2[0]-pos[0]
      y2=pos2[1]-pos[1]
      angle=abs(math.atan2(x1*y2-x2*y1,x1*x2+y1*y2))
      ans[i]=angle/(2*pi)
  for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import math
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
pi=math.pi
hl=[[pi,0,0,-pi] for i in range(n)]
for i in range(n):
    x1,y1=l[i]
    for j in range(i+1,n):
        x2,y2=l[j]
        if x1==x2:
            if y1>y2:
                hl[i][3]=0
                hl[j][0]=0
            else:
                hl[i][0]=0
                hl[j][3]=0
        else:
            r=math.atan((y2-y1)/(x2-x1))+pi/2
            if x2>x1:
                hl[j][3]=max(hl[j][3],r-pi)
                hl[j][0]=min(hl[j][0],r)
                hl[i][1]=max(hl[i][1],r)
                hl[i][2]=min(hl[i][2],r-pi)
            else:
                hl[i][3]=max(hl[i][3],r-pi)
                hl[i][0]=min(hl[i][0],r)
                hl[j][1]=max(hl[j][1],r)
                hl[j][2]=min(hl[j][2],r-pi)
for i in hl:
    a,b,c,d=i
    print((max(0,a-b)+max(0,c-d))/(2*pi))

Submission status: Accepted

Solution code:
import math
from functools import reduce
n = int(input())
xy = []
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append([x, y, i])

def convex_hull_graham(points):
    TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

    def cmp(a, b):
        return (a > b) - (a < b)

    def turn(p, q, r):
        return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)

    def _keep_left(hull, r):
        while len(hull) > 1 and turn(hull[-2], hull[-1], r) == TURN_RIGHT:
            hull.pop()
        if not len(hull) or hull[-1] != r:
            hull.append(r)
        return hull

    points = sorted(points)
    l = reduce(_keep_left, points, [])
    u = reduce(_keep_left, reversed(points), [])
    return l.extend(u[i] for i in range(1, len(u) - 1)) or l

ret = convex_hull_graham(xy)
ret.append(ret[0])
ret.append(ret[1])
thetas = [0.0] * n
for i in range(1, len(ret)-1):
    v1 = [-ret[i][1] + ret[i-1][1], ret[i][0] - ret[i-1][0]]
    v2 = [-ret[i+1][1] + ret[i][1], ret[i+1][0] - ret[i][0]]
    v1_norm = math.sqrt(v1[0]**2.0 + v1[1]**2.0)
    v2_norm = math.sqrt(v2[0]**2.0 + v2[1]**2.0)
    thetas[ret[i][2]] = math.acos((v1[0]*v2[0] + v1[1]*v2[1]) / (v1_norm * v2_norm))
for item in thetas:
    print(item / (math.pi * 2.0))