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

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import acos

def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p2[1]-p1[1])*(p3[0]-p1[0])

def ConvexHull(points):
    u = []
    l = []
    points.sort()
    
    for p in points:
        while len(u)>1 and ccw(u[-2], u[-1], p)>=0:
            u.pop()
        while len(l)>1 and ccw(l[-2], l[-1], p)<=0:
            l.pop()
            
        u.append(p)
        l.append(p)
        
    return u + l[-2:0:-1]


def angle(v1, v2):
    inner = v1[0]*v2[0] + v1[1]*v2[1]
    normv1 = (v1[0]**2 + v1[1]**2) ** 0.5
    normv2 = (v2[0]**2 + v2[1]**2) ** 0.5
    
    return acos(inner / (normv1*normv2))

n = ni()
if n == 1:
    print(1)

elif n == 2:
    print(0.5)
    print(0.5)
    
else:
    points = [list(li()) + [i] for i in range(n)]    
    ch = ConvexHull(points)    
    bsc = []
    
    for i in range(len(ch)):
        x1,y1,i1 = ch[i]
        x2,y2,i2 = ch[i-1]
        
        bsc.append((y1-y2, x2-x1))
        
    if len(ch) == 2:
        angles = [1,1]
        
    else:
        angles = [angle(bsc[i], bsc[i-1]) for i in range(len(ch))]
    
    sm = sum(angles)
        
    ans = [0]*n
    for i in range(len(ch)):
        x,y,ind = ch[i-1]
        ans[ind] = angles[i] / sm
        
    for x in ans:
        print(x)

Solution (Python):
from math import sqrt,pi,acos
n = int(input())
p1 = [[int(i) for i in input().split()] for i in range(n)]
p,q,ans = sorted(p1),[],[]
x1,x2,y1,y2,z1,z2 = p[0][0],p[0][1]+1,p[0][0],p[0][1],10**6+1,0
def cos(a,b,c,d,e,f):
	a,b,e,f = a-c,b-d,e-c,f-d
	return (a*e+b*f)/(sqrt(a**2+b**2)*sqrt(e**2+f**2))
while p[0]!=[z1,z2]:
	q.append([y1,y2])
	num = 2
	for i,j in p:
		if y1!=i or y2!=j:
			m = cos(x1,x2,y1,y2,i,j)
			if num>m: num,z1,z2 = m,i,j
	ans.append((pi-acos(max(-1,num)))/(2*pi))
	x1,x2,y1,y2 = y1,y2,z1,z2
ans = [(pi-acos(cos(x1,x2,y1,y2,q[1][0],q[1][1])))/(2*pi)]+ans[1:]
for i in p1:
	if i in q: print(ans[q.index(i)])
	else: print(0)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def ccw(a, b, c):
    ax = b[0] - a[0]
    ay = b[1] - a[1]
    bx = c[0] - a[0]
    by = c[1] - a[1]
    t = ax*by - ay*bx;
    if t > 0:
        return 1
    if t < 0:
        return -1
    if ax*bx + ay*by < 0:
        return 2
    if ax*ax + ay*ay < bx*bx + by*by:
        return -2
    return 0

def convex_hull(ps):
    n = len(ps)
    k = 0
    ps.sort()
    ch = [None] * (n*2)
    for i in range(n):
        while k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    t = k + 1
    for i in range(n-2,-1,-1):
        while k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1

    return ch[:k-1]

def radian(a, b):
    return math.atan2(b[1]-a[1], b[0]-a[0])

def main():
    n = I()
    a = [LI() + [_] for _ in range(n)]
    t = convex_hull(a)
    l = len(t)
    r = [0] * n
    if l == 2:
        r[t[0][2]] = 0.5
        r[t[1][2]] = 0.5
    else:
        for i in range(l):
            r1 = radian(t[i], t[i-1])
            r2 = radian(t[i], t[(i+1) % l])
            k = r2 - r1
            while k < 0:
                k += math.pi * 2
            e = (k-math.pi) / math.pi / 2
            r[t[i][2]] = e

    return '\n'.join(map(str,r))


print(main())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def ccw(a, b, c):
    ax = b[0] - a[0]
    ay = b[1] - a[1]
    bx = c[0] - a[0]
    by = c[1] - a[1]
    t = ax*by - ay*bx;
    if t > 0:
        return 1
    if t < 0:
        return -1
    if ax*bx + ay*by < 0:
        return 2
    if ax*ax + ay*ay < bx*bx + by*by:
        return -2
    return 0

def convex_hull(ps):
    n = len(ps)
    k = 0
    ps.sort()
    ch = [[-1,-1] for _ in range(n*2)]
    for i in range(n):
        while k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    t = k + 1
    for i in range(n-2,-1,-1):
        while k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    ch = ch[:k-1]
    return ch

def radian(a, b):
    return math.atan2(b[1]-a[1], b[0]-a[0])

def main():
    n = I()
    a = [LI() + [_] for _ in range(n)]
    t = convex_hull(a)
    l = len(t)
    r = [0] * n
    if l == 2:
        r[t[0][2]] = 0.5
        r[t[1][2]] = 0.5
    else:
        for i in range(l):
            r1 = radian(t[i], t[i-1])
            r2 = radian(t[i], t[(i+1) % l])
            k = r2 - r1
            while k < 0:
                k += math.pi * 2
            e = (k-math.pi) / math.pi / 2
            r[t[i][2]] = e

    return '\n'.join(map(str,r))


print(main())

Solution (Python):
import math
import cmath

def arg(center, point):
	return cmath.phase(complex(point[0] - center[0], point[1] - center[1]))

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

if n == 2:
	print(0.5)
	print(0.5)
else:
	ans = []
	for d in dots:
		arg_list = []
		for e in dots:
			if d == e:
				continue
			else:
				arg_list.append(arg(d, e))
		arg_list.sort()
		convex = False
		if arg_list[-1] - arg_list[0] <= math.pi:
			convex = True
			theta = arg_list[-1] - arg_list[0]
			ans.append(0.5 - theta / (2 * math.pi))
		else:
			for i in range(len(arg_list) - 1):
				if arg_list[i + 1] - arg_list[i] >= math.pi:
					convex = True
					theta = arg_list[i + 1] - arg_list[i]
					ans.append(theta / (2 * math.pi) - 0.5)
			if convex == False:
				ans.append(0)

	for a in ans:
		print(a)

Solution (Python):
import math
import cmath







def arg(center, point):
	return cmath.phase(complex(point[0] - center[0], point[1] - center[1]))


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

if n == 2:
	print(0.5)
	print(0.5)
else:
	ans = []
	for d in dots:
		arg_list = []
		for e in dots:
			if d == e:
				continue
			else:
				arg_list.append(arg(d, e))
		arg_list.sort()
		convex = False
		if arg_list[-1] - arg_list[0] <= math.pi:
			convex = True
			theta = arg_list[-1] - arg_list[0]
			ans.append(0.5 - theta / (2 * math.pi))
		else:
			for i in range(len(arg_list) - 1):
				if arg_list[i + 1] - arg_list[i] >= math.pi:
					convex = True
					theta = arg_list[i + 1] - arg_list[i]
					ans.append(theta / (2 * math.pi) - 0.5)
			if convex == False:
				ans.append(0)

	for a in ans:
		print(a)

Solution (Python):
import math
N = int(input())
H = [list(map(int, input().split())) for i in range(N)]
P = [[0, 2*math.pi] for i in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        rad = math.atan2(H[i][1]-H[j][1], H[i][0]-H[j][0])
        mi = (rad - math.pi/2) % (2*math.pi)
        ma = (rad + math.pi/2) % (2*math.pi)
        if ma > mi:
            if P[i][0] >= P[i][1]:
                if mi < P[i][1]:
                    P[i] = [mi, P[i][1]]
                elif ma > P[i][0]:
                    P[i] = [P[i][0], ma]
                else:
                    P[i] = [0, 0]
                    break
            else:
                P[i] = [max(P[i][0], mi), min(P[i][1], ma)]
                if P[i][0] >= P[i][1]:
                    P[i] = [0, 0]
                    break
        else:
            if P[i][0] >= P[i][1]:
                P[i] = [max(P[i][0], mi), min(P[i][1], ma)]
            elif P[i] == [0, 2*math.pi]:
                P[i] = [mi, ma]
            else:
                if mi < P[i][1]:
                    if mi < P[i][0]:
                        continue
                    else:
                        P[i] = [mi, P[i][1]]
                elif ma > P[i][0]:
                    if ma > P[i][1]:
                        continue
                    else:
                        P[i] = [P[i][0], ma]
                else:
                    P[i] = [0, 0]
                    break
for p in P:
    print((p[1]-p[0]) / (2*math.pi) % 1)

Solution (Python):
import numpy as np
from collections import defaultdict

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

n = int(input())
H = [np.array([int(j) for j in input().split()]) for i in range(n)]

convex = [min(H, key=lambda x:x[1])]

for i in range(n):
    a = H[0] if (H[0] != convex[-1]).any() else H[-1]
    for b in H:
        ac = a-convex[-1]
        bc = b-convex[-1]
        cross_ = cross(ac, bc)
        if cross_ < 0 or (cross_ == 0 and np.linalg.norm(ac) < np.linalg.norm(bc)):
            a = b
    if (a == convex[0]).all():
        break
    convex.append(a)

ans = defaultdict(float)

for c, a, b in zip([convex[-1]]+convex[:-1], convex, convex[1:] + [convex[0]]):
    ca = c-a
    ba = b-a
    i = np.inner(ca, ba)
    n = np.linalg.norm(ca) * np.linalg.norm(ba)
    ans[tuple(a)] = (np.pi - np.arccos(np.clip(i/n, -1, 1))) / (2*np.pi)

for i in H:
    print(ans[tuple(i)])

Solution (Python):
from numpy import argmax
import numpy as np
from collections import defaultdict

cross = np.cross

n = int(input())
H = [np.array([int(j) for j in input().split()]) for i in range(n)]

if n == 1:
    print(1)
    exit()





convex = [min(H, key=lambda x:x[1])]

for i in range(n):
    a = H[0] if (H[0] != convex[-1]).any() else H[-1]
    for b in H:
        ac = a-convex[-1]
        bc = b-convex[-1]
        cross_ = cross(ac, bc)
        if cross_ < 0 or (cross_ == 0 and np.linalg.norm(ac) < np.linalg.norm(bc)):
            a = b
    if (a == convex[0]).all():
        break
    convex.append(a)

ans = defaultdict(float)

for c, a, b in zip([convex[-1]]+convex[:-1], convex, convex[1:] + [convex[0]]):
    ca = c-a
    ba = b-a
    i = np.inner(ca, ba)
    n = np.linalg.norm(ca) * np.linalg.norm(ba)
    ans[tuple(a)] = (np.pi - np.arccos(np.clip(i/n, -1, 1))) / (2*np.pi)

for i in H:
    print(ans[tuple(i)])

Solution (Python):
from numpy import argmax
import numpy as np
from collections import defaultdict

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

n = int(input())
H = [np.array([int(j) for j in input().split()]) for i in range(n)]

if n == 1:
    print(1)
    exit()





convex = [min(H, key=lambda x:x[1])]

for i in range(n):
    a = H[0] if (H[0] != convex[-1]).any() else H[-1]
    for b in H:
        ac = a-convex[-1]
        bc = b-convex[-1]
        cross_ = cross(ac, bc)
        if cross_ < 0 or (cross_ == 0 and np.linalg.norm(ac) < np.linalg.norm(bc)):
            a = b
    if (a == convex[0]).all():
        break
    convex.append(a)

ans = defaultdict(float)

for c, a, b in zip([convex[-1]]+convex[:-1], convex, convex[1:] + [convex[0]]):
    ca = c-a
    ba = b-a
    i = np.inner(ca, ba)
    n = np.linalg.norm(ca) * np.linalg.norm(ba)
    ans[tuple(a)] = (np.pi - np.arccos(np.clip(i/n, -1, 1))) / (2*np.pi)

for i in H:
    print(ans[tuple(i)])

Solution (Python):
from numpy import argmax
import numpy as np
from collections import defaultdict

n = int(input())
H = [np.array([int(j) for j in input().split()]) for i in range(n)]

if n == 1:
    print(1)
    exit()





convex = [min(H, key=lambda x:x[1])]

for i in range(n):
    a = H[0] if (H[0] != convex[-1]).any() else H[-1]
    for b in H:
        ac = a-convex[-1]
        bc = b-convex[-1]
        cross_ = np.cross(ac, bc)
        if cross_ < 0 or (cross_ == 0 and np.linalg.norm(ac) < np.linalg.norm(bc)):
            a = b
    if (a == convex[0]).all():
        break
    convex.append(a)

ans = defaultdict(float)

for c, a, b in zip([convex[-1]]+convex[:-1], convex, convex[1:] + [convex[0]]):
    ca = c-a
    ba = b-a
    i = np.inner(ca, ba)
    n = np.linalg.norm(ca) * np.linalg.norm(ba)
    ans[tuple(a)] = (np.pi - np.arccos(np.clip(i/n, -1, 1))) / (2*np.pi)

for i in H:
    print(ans[tuple(i)])

Solution (Python):
from numpy import argmax
import numpy as np
from collections import defaultdict

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

n = int(input())
H = [np.array([int(j) for j in input().split()]) for i in range(n)]

if n == 1:
    print(1)
    exit()





convex = [min(H, key=lambda x:x[1])]

for i in range(n):
    a = H[0] if (H[0] != convex[-1]).any() else H[-1]
    for b in H:
        ac = a-convex[-1]
        bc = b-convex[-1]
        cross_ = cross(ac, bc)
        if cross_ < 0 or (cross_ == 0 and np.linalg.norm(ac) < np.linalg.norm(bc)):
            a = b
    if (a == convex[0]).all():
        break
    convex.append(a)

ans = defaultdict(float)

for c, a, b in zip([convex[-1]]+convex[:-1], convex, convex[1:] + [convex[0]]):
    ca = c-a
    ba = b-a
    i = np.inner(ca, ba)
    n = np.linalg.norm(ca) * np.linalg.norm(ba)
    ans[tuple(a)] = (np.pi - np.arccos(np.clip(i/n, -1, 1))) / (2*np.pi)

for i in H:
    print(ans[tuple(i)])

Solution (Python):
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
MP = {tuple(p): i for i, p in enumerate(P)}

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

from math import atan2, pi

Q = convex_hull(P)[:-1]
K = len(Q)
ans = [0.]*N
for i in range(K):
    S = Q[i-1]; T = Q[i]; U = Q[(i+1)%K]
    X0 = T[0] - S[0]; X1 = U[0] - T[0]
    Y0 = T[1] - S[1]; Y1 = U[1] - T[1]
    ans[MP[tuple(Q[i])]] = atan2(X1*Y0 - X0*Y1, X0*X1 + Y0*Y1) / 2. / pi
print(*ans, sep='\n')

Solution (Python):


import sys, math, copy

import numpy as np


HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    nt = 200000
    n = int(input())
    xy = np.empty((2, n))
    for i in range(n):
        x, y = map(int, input().split())
        xy[:, i] = [x, y]
    x_rot = np.zeros((nt, n))
    thetas = np.linspace(0, 2.0 * np.pi, nt, endpoint=False)
    cnt = [0 for i in range(n)]
    for i in range(n):
        x_rot[:, i] = xy[0, i] * np.cos(thetas) - xy[1, i] * np.sin(thetas)
    am = np.argmax(x_rot, axis=1)
    for t in range(nt):
        cnt[am[t]] += 1
    for i in range(n):
        print("%.10f" % (cnt[i] / nt))

main()

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


def vec(pi, pj):
  return (pj[0] - pi[0], pj[1] - pi[1])

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)


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))

Solution (Python):
from collections import Counter

import numpy as np


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

    div = 200000
    a = np.linspace(0, 2 * np.pi, div, endpoint=False)
    b = np.array([np.cos(a), np.sin(a)], dtype=np.float32)
    for i, v in Counter(np.argmax(np.dot(pts, b), axis=0)).items():
        ans[i] = v / div
    return ans


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

Solution (Python):
import math


def ccw(p0, p1, p2):
    return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p1[1] - p0[1]) * (p2[0] - p0[0])


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


pts.sort()

chU = [] 
for pt, i in pts:
    while len(chU) >= 2 and ccw(chU[-2][0], chU[-1][0], pt) >= 0:
        chU.pop()
    chU.append((pt, i))

chL = [] 
for pt, i in reversed(pts):
    while len(chL) >= 2 and ccw(chL[-2][0], chL[-1][0], pt) >= 0:
        chL.pop()
    chL.append((pt, i))

CH = chU[:-1] + chL[:-1] 




aIn = math.atan2(CH[-1][0][1] - CH[0][0][1], CH[-1][0][0] - CH[0][0][0])
ptNow = CH[-1][0]
anss = [0.0] * N
for i in reversed(range(len(CH))):
    iNow = CH[i][1]
    pt2 = CH[i - 1][0]
    aOut = math.atan2(pt2[1] - ptNow[1], pt2[0] - ptNow[0])
    anss[iNow] = ((aOut - aIn) % (2 * math.pi)) / (2 * math.pi)

    ptNow = pt2
    aIn = aOut

for ans in anss:
    print(ans)

Solution (Python):
from math import atan2,pi

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
ptoi = {}
for i,p in enumerate(src):
    ptoi[p] = i

if N == 2:
    for i in range(2): print(0.5)
    exit()


def convex_hull(ps):
    ps.sort()
    def cross(o,a,b):
        return (a[0]-o[0]) * (b[1]-o[1]) - (a[1]-o[1]) * (b[0]-o[0])
    lower = []
    for p in ps:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(ps):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

outer = convex_hull(src)
outer += outer[:2]

ans = [0] * N
for (y1,x1),(y2,x2),(y3,x3) in zip(outer,outer[1:],outer[2:]):
    dy1,dx1 = y2-y1,x2-x1
    dy2,dx2 = y3-y2,x3-x2
    ang1 = atan2(dx1, dy1)
    ang2 = atan2(dx2, dy2)
    a = (ang2 - ang1) % (pi*2) / (pi*2)
    ans[ptoi[(y2,x2)]] = a

for a in ans:
    print(a)

Solution (Python):
from math import atan2, degrees

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

for x, y in holes:
    slopes = []
    for x2, y2 in holes:
        if x == x2 and y == y2: continue
        slopes += [degrees(atan2(y2 - y, x2 - x))]

    aRange = [(0, 360)]
    for slope in slopes:
        f1 = (slope + 90) % 360
        t1 = (slope - 90) % 360
        if t1 == 0: t1 = 360

        if f1 <= t1:
            fts = [(f1, t1)]
        else:
            fts = [(0, t1), (f1, 360)]

        aRange2 = []
        for f, t in fts:
            for aFr, aTo in aRange:
                if aFr <= f: aFr = f
                if t <= aTo: aTo = t
                if aFr <= aTo:
                    aRange2 += [(aFr, aTo)]
        aRange = aRange2

    ans = 0
    for aFr, aTo in aRange:
        ans += (aTo - aFr) / 360
    print(ans)

Solution (Python):
import math
import random
N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
suma = 0
for i in range(N):
    r = []
    for j in range(N):
        if i == j:
            continue
        r.append(math.atan2(Y[j] - Y[i], X[j] - X[i]))
    r.sort()
    dr = [r[i + 1] - r[i] for i in range(len(r) - 1)]
    dr.append(r[0] + 2 * math.pi - r[-1])
    print((max(dr) - math.pi) / (2 * math.pi) if max(dr) > math.pi else 0)

Solution (Python):
from collections import Counter
import numpy as np

p = 2.5e5
n = int(input())
l = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.float32)
ans = np.zeros(n)

a = np.linspace(0, 2 * np.pi, p, endpoint=False)
b = np.array([np.sin(a), np.cos(a)], dtype=np.float32)

for i, v in Counter(np.argmax(np.dot(l, b), axis=0)).items():
  ans[i] += v / p

print('\n'.join(map(str, ans)))

Solution (Python):
from collections import Counter
import numpy as np


def part(s, t):
    a = np.linspace(s, t, 1e5, endpoint=False)
    for i, v in Counter(np.argmax(np.dot(pts, [np.sin(a), np.cos(a)]), axis=0)).items():
        ans[i] += v


n = int(input())
pts = [list(map(int, input().split())) for _ in range(n)]
ans = np.zeros(n)
part(0, np.pi)
part(np.pi, 2 * np.pi)
ans /= 2e5
print('\n'.join(map(str, ans)))

Solution (Python):
from collections import Counter
import numpy as np


def part(pts, s, t, num, ans):
    a = np.linspace(s, t, num, endpoint=False)
    for i, v in Counter(np.argmax(np.dot(pts, [np.sin(a), np.cos(a)]), axis=0)).items():
        ans[i] += v


def solve(n, pts):
    ans = np.zeros(n)
    part(pts, 0, np.pi, 1e5, ans)
    part(pts, np.pi, 2 * np.pi, 1e5, ans)
    return ans / 2e5


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

Solution (Python):
from collections import Counter

import numpy as np


def part(pts, a, ans):
    b = np.dot(pts, [np.sin(a), np.cos(a)])
    c = np.argmax(b, axis=0)
    for i, v in Counter(c).items():
        ans[i] += v


def solve(n, pts):
    ans = [0] * n
    part(pts, np.linspace(0, np.pi, 100000, endpoint=False), ans)
    part(pts, np.linspace(np.pi, 2 * np.pi, 100000, endpoint=False), ans)
    return [v / 200000 for v in ans]


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

Solution (Python):
import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.qhull import QhullError


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

    try:
        hull = ConvexHull(pts)
    except QhullError:
        lm = np.argmin(pts, axis=0)
        rm = np.argmax(pts, axis=0)
        if lm[0] != rm[0]:
            l, r = lm[0], rm[0]
        elif lm[1] != rm[0]:
            l, r = lm[1], rm[0]
        else:
            l, r = lm[0], rm[1]
        ans[l] = ans[r] = 0.5
        return ans

    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

    for i, a in zip(hull.vertices, da):
        ans[i] = a

    return ans


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

Solution (Python):


import numpy as np

n = int(raw_input())
p = np.zeros([n,2],dtype=int)
for i in range(n):
    p[i] = map(int,raw_input().split())



s = np.zeros([n])

for i in range(n):
    katamuki = np.zeros([n])
    for j in range(n):
        if not i == j:
            vec = np.array([p[j][0]-p[i][0],p[j][1]-p[i][1]])
            xvec = np.array([1,0])
            katamuki[j] = np.arccos((np.dot(xvec,vec))/(np.linalg.norm(vec)))
        if p[j][1]-p[i][1] < 0:
            katamuki[j] = 2*np.pi - katamuki[j]
    
    katamuki = np.sort(katamuki)
    for j in range(n-1):
        if j == 0:
            kakudo = katamuki[1]+(2*np.pi-katamuki[n-1])
        else:
            kakudo = katamuki[j+1]-katamuki[j]
        if kakudo > np.pi:
            s[i] = kakudo-np.pi


ans = s / (2*np.pi)

for line in ans:
    print line

Solution (Python):
import math
N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
    x[i], y[i] = map(int, input().split())


def mindis(t):
    j = 0
    for i in range(N):
        if x[i]*math.cos(t)+y[i]*math.sin(t)<x[j]*math.cos(t)+y[j]*math.sin(t):
            j = i
    return j


r = [0 for i in range(N)]
M = 250000
for i in range(M):
    k = mindis(2*math.pi*i/M)
    r[k] += 1
S = sum(r)
for i in range(N):
    print(r[i]/S)

Solution (Python):
from sys import exit, stderr, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
from math import atan2, pi

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

p = []

N = read()

for _ in range(N):
  (x, y) = reads()
  p.append((x, y))

for i in range(N):
  (x, y) = p[i]
  (b1, e1) = (0, pi)
  (b2, e2) = (pi, 2*pi)

  for j in range(N):
    if j == i:
      continue

    (z, w) = p[j]
    th = (atan2(w - y, z - x) + pi / 2) % (2*pi)

    if th <= pi:
      b1 = max(b1, th)
      e2 = min(e2, th + pi)
    else:
      e1 = min(e1, th - pi)
      b2 = max(b2, th)
  result = (max(0, e1-b1) + max(0, e2-b2)) / 2 / pi
  print("{:.20f}".format(result))

Solution (Python):
import math

N=int(input())

PI = math.pi

X=[]
Y=[]
for i in range(N):
    x,y=[int(i) for i in input().split()]
    X.append(x)
    Y.append(y)

for i in range(N):
    kakudo = [math.atan2(Y[i]-Y[j],X[i]-X[j]) for j in range(N) if j != i]
    kakudo.sort()

    kmax = 0
    if N == 2:
        kmax = 2*PI
    else:
        for j in range(N-2):
            kmax = max(kmax,kakudo[j+1] - kakudo[j])
            kmax = max(kmax, kakudo[0] + 2*PI - kakudo[N-2])
    print(max(0,kmax-PI)/(2*PI))

Solution (Python):
import math
from math import pi

def solve(rng_lst, N):
    pos_lst = [] 
    for rng in rng_lst:
        pos_lst.append((rng[0], rng[2], True))
        pos_lst.append((rng[1], rng[2], False))
    pos_lst = sorted(pos_lst, key=lambda x: x[0])
    
    ans = 0
    opp_lst = []
    prv = 0
    for pos in pos_lst:
        if pos[2]: 
            opp_lst.append(pos[1])
        else: 
            if len(opp_lst) == N - 1:
                ans += (pos[0] - prv)
            opp_lst.remove(pos[1])
        prv = pos[0]
    return ans/(2*pi)

N = int(input())
x_lst = []
y_lst = []
for _ in range(N):
    x, y = [int(_) for _ in input().split()]
    x_lst.append(x)
    y_lst.append(y)
    
for i in range(N):
    rng_lst = [] 
    for j in range(N):
        if i != j:
            xi = x_lst[i]
            yi = y_lst[i]
            xj = x_lst[j]
            yj = y_lst[j]
            
            if yi == yj:
                if (xi < xj):
                    rng_lst.append((pi / 2,  pi / 2 + pi, j))
                else:
                    rng_lst.append((0, pi / 2, j))
                    rng_lst.append((pi / 2 + pi, 2 * pi, j))
            else:
                k = - (xj - xi) / (yj - yi)
                xii = xi - (xi + xj)/2
                yii = yi - (yi + yj)/2
                at = math.atan(k)

                if at >= 0 and yii < k * xii:
                    rng_lst.append((0, at, j))
                    rng_lst.append((pi + at, 2 * pi, j))
                elif at >= 0 and yii > k * xii:
                    rng_lst.append((at, pi + at, j))
                elif at < 0 and yii < k * xii:
                    rng_lst.append((pi + at, 2 * pi + at, j))
                elif at < 0 and yii > k * xii:
                    rng_lst.append((0, pi + at, j))
                    rng_lst.append((2 * pi + at, 2 * pi, j))
                else:
                    print(k, xii, yii, at)
                    assert 0 == 1
    print(solve(rng_lst, N))

Solution (Python):
from math import atan2, pi
n = int(raw_input())
a = [map(int, raw_input().split()) for _ in xrange(n)]
for i in xrange(n):
    x, y = a[i]
    p = []
    for j in xrange(n):
        if i == j:
            continue
        nx, ny = a[j]
        t = atan2(y - ny, x - nx)
        if t - pi / 2 < -pi:
            p.append((-pi, 1))
            p.append((t + pi / 2, -1))
            p.append((t - pi / 2 + 2 * pi, 1))
            p.append((pi, -1))
        elif t + pi / 2 > pi:
            p.append((-pi, 1))
            p.append((t + pi / 2 - 2 * pi, -1))
            p.append((t - pi / 2, 1))
            p.append((pi, -1))
        else:
            p.append((t - pi / 2, 1))
            p.append((t + pi / 2, -1))
    p.sort()
    pv = -pi
    tot = 0
    c = 0
    for x, y in p:
        if c == n - 1:
            tot += x - pv
        c += y
        pv = x
    print "%.12f" % (tot / 2 / pi,)

Solution (Python):
MIS = lambda: map(int,input().split())
from math import acos

def ccw(p1, p2, p3):
    
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p2[1]-p1[1])*(p3[0]-p1[0])

def ConvexHull(p):
    U = []; L = []; p.sort()
    for q in p:
        while len(U)>1 and ccw(U[-2], U[-1], q) >= 0: U.pop()
        while len(L)>1 and ccw(L[-2], L[-1], q) <= 0: L.pop()
        U.append(q); L.append(q)
    return U + L[-2:0:-1]

def angle(v1, v2):
    inner = v1[0]*v2[0] + v1[1]*v2[1]
    v1s = (v1[0]**2 + v1[1]**2) ** .5
    v2s = (v2[0]**2 + v2[1]**2) ** .5
    return acos(inner / v1s / v2s)

n = int(input())
if n == 1: print(1); exit()
if n == 2: print(0.5); print(0.5); exit()

p = [tuple(MIS())+(i,) for i in range(n)]
CH = ConvexHull(p)
bsc = []
for i in range(len(CH)):
    x1, y1, i1 = CH[i]
    x2, y2, i2 = CH[i-1]
    bsc.append((y1-y2, x2-x1))
if len(CH) == 2: angles = [1, 1]
else: angles = [angle(bsc[i], bsc[i-1]) for i in range(len(CH))]
S = sum(angles)

ans = [0] * n
for i in range(len(CH)):
    x, y, ind = CH[i-1]
    ans[ind] = angles[i] / S
for x in ans: print(x)