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 numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.qhull import QhullError
from scipy.spatial.distance import cosine

def main(points):
    ans = [0.0] * N

    try:
        hull = ConvexHull(np.asarray(points))
    except QhullError:
        ans[points.index(min(points))] = ans[points.index(max(points))] = 0.5
        return ans

    L = hull.vertices.shape[0]

    for i, v in enumerate(hull.vertices):
        prv, nxt = hull.vertices[[(i+L-1) % L, (i+1) % L]]
        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


if __name__ == '__main__':
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append([x, y])
    print(*main(points), sep='\n')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from math import atan2,pi

def InnerProduct(V0,V1):
    x0,y0=V0
    x1,y1=V1
    return x0*x1+y0*y1
def CrossProduct(V0,V1):
    x0,y0=V0
    x1,y1=V1
    return x0*y1-x1*y0
def clockwise(P0,P1,P2):
    V0,V1=(P1[0]-P0[0],P1[1]-P0[1]),(P2[0]-P0[0],P2[1]-P0[1])
    return CrossProduct(V0,V1)<0

def MonotoneChain(V):
    upper,lower=[],[]
    P=sorted(V)
    for p in P:
        while len(lower)>1 and (not clockwise(lower[-2],lower[-1],p)):
            lower.pop()
        lower.append(p)
    for p in P[::-1]:
        while len(upper)>1 and (not clockwise(upper[-2],upper[-1],p)):
            upper.pop()
        upper.append(p)
    return lower[:-1]+upper[:-1]

n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]
d={p: i for i,p in enumerate(P)}
ans=[0]*n
CH=MonotoneChain(P)
CH+=[CH[0],CH[1]]
for (x0,y0),(x1,y1),(x2,y2) in zip(CH,CH[1:],CH[2:]):
    V0,V1=(x0-x1,y0-y1),(x2-x1,y2-y1)
    ans[d[(x1,y1)]]=(pi-atan2(CrossProduct(V0,V1),InnerProduct(V0,V1)))/(2*pi)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import math

n = int(input())
ps = [tuple(map(int, input().split())) for _ in range(n)]
mp = {tuple(p): i for i, p in enumerate(ps)}

# ベクトルp0p1に対する点p2の位置（反時計回り, もしくは直線上ならTrue, 時計回りならFalse）を返す。
def ccw(p0, p1, p2):
    return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p1[1] - p0[1]) * (p2[0] - p0[0]) >= 0   # (ベクトルp0p1とベクトルp0p2の外積) >= 0

# 凸包を求める。psは点(x, y)の集合。
def convex_hull(ps):
    upper = []
    lower = []
    ps.sort()
    for p in ps:
        while len(lower) > 1 and ccw(lower[-2], lower[-1], p):
            lower.pop()
        lower.append(p)

    for p in ps[::-1]:
        while len(upper) > 1 and ccw(upper[-2], upper[-1], p):
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

ans = [0] * n
ch = convex_hull(ps)
ch += [ch[0]]
ch += [ch[1]]

for pre, now, next in zip(ch, ch[1:], ch[2:]):
    x0 = now[0] - pre[0]
    y0 = now[1] - pre[1]
    x1 = next[0] - now[0]
    y1 = next[1] - now[1]
    ans[mp[tuple(now)]] = math.atan2(x1*y0 - x0*y1, x0*x1 + y0*y1) / (2 * math.pi)  # atan2(外積, 内積), 外積: |u||v|sinθ, 内積: |u||v|cosθ

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import math

n = int(input())
c = [[0]*2 for i in range(n) ]
a = [0] * n
p = math.pi
for i in range(n):
    c[i][0], c[i][1] = map(float, input().split())

def f(ax, ay, bx, by, cx, cy):
    vx = ax - cx
    vy = ay - cy
    wx = bx - cx
    wy = by - cy
    s = 1
    if vx * wy - vy * wx < 0: s = -1
    p = vx * wx + vy * wy
    q = ( vx * vx + vy * vy ) ** 0.5
    r = ( wx * wx + wy * wy ) ** 0.5
    t = p / (q * r)
    t = max(-1, min(1, t))
    t = (math.acos( t )) * s
    return t

for i in range(n):
    k = (i+1)%n
    tax = 0
    tin = 0
    for j in range(n):
        if j != i and j != k:
            t = f(c[k][0], c[k][1], c[j][0], c[j][1], c[i][0], c[i][1])
            tax = max(tax, t)
            tin = min(tin, t)
    if tax - tin < p:
        a[i] = (p - tax + tin) / (p * 2)

for i in range(n):
    print(round(a[i], 6))

Submission status: Accepted

Solution code:
from math import pi, atan2

def andrange(a, b):
    if a == (0, 0) or b == (0, 0): return (0, 0)
    if a == (0, 1): return b
    if b == (0, 1): return a
    if a[0] > b[0]: a, b = b, a
    if b[1] < a[1]: return b
    if b[0] < a[1]: return (b[0], a[1])
    if b[1] < a[0] + 1: return (0, 0)
    if b[1] < a[1] + 1: return (a[0], b[1] - 1)
    return a

def calcrange(P, Q):
    c = atan2(P[1]-Q[1], P[0]-Q[0]) / (2*pi)
    if c > 0: return (c, c+0.5)
    else: return (c+1, c+1.5)

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

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

for i in range(N):
    for j in range(N):
        if i != j:
            A[i] = andrange(A[i], calcrange(X[i], X[j]))

for a in A:
    print("{:.15f}".format(a[1] - a[0]))

Submission status: Accepted

Solution code:
from math import pi, atan2

def andrange(a, b):
    if a == (0, 0) or b == (0, 0): return (0, 0)
    if a == (0, 1): return b
    if b == (0, 1): return a
    if a[0] > b[0]: a, b = b, a
    if b[1] < a[1]: return b
    if b[0] < a[1]: return (b[0], a[1])
    if b[1] < a[0] + 1: return (0, 0)
    if b[1] < a[1] + 1: return (a[0], b[1] - 1)
    return a

def calcrange(P, Q):
    c = atan2(P[1]-Q[1], P[0]-Q[0]) / (2*pi)
    if c > 0: return (c, c+0.5)
    else: return (c+1, c+1.5)

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

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

for i in range(N):
    for j in range(N):
        if i != j:
            A[i] = andrange(A[i], calcrange(X[i], X[j]))

for a in A:
    print("{:.15f}".format(a[1] - a[0]))

Submission status: Accepted

Solution code:
import math
pi = math.atan(1)*4

def andrange(a, b):
    if a == (0, 0) or b == (0, 0): return (0, 0)
    if a == (0, 1): return b
    if b == (0, 1): return a
    if a[0] > b[0]: a, b = b, a
    if b[1] < a[1]:
        return b
    if b[0] < a[1] and b[1] >= a[1]:
        return (b[0], a[1])
    if b[0] >= a[1] and b[1] < a[0] + 1:
        return (0, 0)
    if b[1] >= a[0] + 1 and b[1] < a[1] + 1:
        return (a[0], b[1] - 1)
    if b[1] >= a[0] + 1 and b[1] >= a[1] + 1:
        return a

def calcrange(P, Q):
    c = calc(P, Q)
    if c > 0:
        return (c, c+0.5)
    else:
        return (c+1, c+1.5)

def calc(P, Q):
    x = P[0] - Q[0]
    y = P[1] - Q[1]
    if x == 0:
        return 0.25 if y > 0 else -0.25
    t = math.atan(y/x)
    return t/(2*pi) if x > 0 else (t/(2*pi) % 1) - 0.5

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

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

for i in range(N):
    for j in range(N):
        if i != j:
            A[i] = andrange(A[i], calcrange(X[i], X[j]))

for a in A:
    print("{:.20f}".format(a[1] - a[0]))

Submission status: Accepted

Solution code:
import math;q=2*math.pi
from cmath import phase as h
t=lambda x:h(x)+(q if 0>h(x)else 0)
n=int(input())
r=range(n)
c=[complex(input().replace(' -', '-').replace(' ','+')+"j")for _ in r]
for i in r:a=sorted([t(c[j]-c[i])/q for j in r if j!=i]);d=[a[j]-a[j-1] for j in r[:-1]];d[0]+=1;print(max(max(d)-1/2,0))

Submission status: Accepted

Solution code:
from math import pi,atan2
q = 2*pi
def deg(a,b):
    d = b-a
    t = atan2(d.real, d.imag)
    if t<0: t += q
    return t
n = int(input())
cs = []
for _ in range(n):
    a,b = map(int,input().split())
    cs += [complex(a,b)]
for i in range(n):
    args = [deg(cs[i],cs[j])/q for j in range(n) if j!=i]
    args = sorted(args)
    dif = [args[i]-args[i-1] for i in range(n-1)]
    dif[0] += 1
    print(max(max(dif) - 1/2, 0))

Submission status: Accepted

Solution code:
from math import atan2,pi
N=int(input())
points=[[int(i) for i in input().split()] for i in range(N)]
p=[0]*N

for i in range(N):
  angle_p=[]
  angle_n=[]
  for j in range(N):
    if i!=j:
      c=atan2(points[i][1]-points[j][1],points[i][0]-points[j][0])
      if c>=0:
        angle_p.append(c)
      else:
        angle_n.append(c)
 
  if len(angle_n)==0:
    d=max(angle_p)-min(angle_p)
  elif len(angle_p)==0:
    d=max(angle_n)-min(angle_n)
  elif max(angle_p)-min(angle_n)<pi:
    d=max(angle_p)-min(angle_n)
  elif pi-min(angle_p)+max(angle_n)<0:
    d=2*pi-min(angle_p)+max(angle_n)
  else:
    d=pi
  p[i]=(pi-d)/(2*pi)
    
for i in range(N):
  print(p[i])

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC021 B
"""

import math
from collections import defaultdict

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


def dist(rad, p):
    radtmp = 2*math.pi*rad/maxcut
    return -p[0]*math.cos(radtmp)-p[1]*math.sin(radtmp)


def closest(rad):
    tmp = dist(rad, ps[0])
    itmp = 0
    for i, pp in enumerate(ps):
        tmp2 = dist(rad, pp)
        if tmp2 < tmp:
            itmp = i
            tmp = tmp2
    return itmp


maxcut = 2**20


binary = defaultdict(int)
binary[0] = closest(0)
binary[maxcut] = binary[0]
binary[maxcut//2] = closest(maxcut//2)
binary[maxcut//4] = closest(maxcut//4)
binary[3*maxcut//4] = closest(3*maxcut//4)


def fillbinary(ll, rr):
    if binary[ll] != binary[rr] and rr-ll != 1:
        mm = (ll+rr)//2
        binary[mm] = closest(mm)
        fillbinary(ll, mm)
        fillbinary(mm, rr)


fillbinary(0, maxcut//4)
fillbinary(maxcut//4, maxcut//2)
fillbinary(maxcut//2, 3*maxcut//4)
fillbinary(3*maxcut//4, maxcut)


binkeys = sorted(binary.keys())
ansli = [0]*n
beforekey = 0
for i in binkeys:
    ansli[binary[i]] += i-beforekey
    beforekey = i


for i in range(n):
    print(ansli[i]/maxcut)

Submission status: Accepted

Solution code:
import math
import sys
def cross(a, b):
	return a[0]*b[1]-a[1]*b[0]
def dot(a, b):
	return a[0]*b[0]+a[1]*b[1]
def counterclockwise(a, b):
	return cross(a, b)<0
def sub(a, b):
	return [a[0]-b[0], a[1]-b[1]]
n=input()
p=[map(int, raw_input().split()) for i in range(n)]
index={tuple(p[i]): i for i in range(n)}
p.sort()
hull=[p[0]]
min_size=1
for i in range(1, n):
	while len(hull)>min_size and not counterclockwise(sub(p[i], hull[-1]), sub(hull[-1], hull[-2])):
		del hull[-1]
	hull.append(p[i])
assert hull[-1]==p[-1]
min_size=len(hull)
for i in range(n-2, -1, -1):
	while len(hull)>min_size and not counterclockwise(sub(p[i], hull[-1]), sub(hull[-1], hull[-2])):
		del hull[-1]
	hull.append(p[i])
assert hull[0]==hull[-1]==p[0]
del hull[-1]
result=[0.0]*n
print>>sys.stderr, hull
for i in range(len(hull)):
	a=sub(hull[(i+1)%len(hull)], hull[i])
	b=sub(hull[i], hull[i-1])
	value=dot(a, b)/math.sqrt(dot(a, a))/math.sqrt(dot(b, b))
	value=min(max(value, -1.0), 1.0)
	angle=math.acos(value)
	result[index[tuple(hull[i])]]=angle
for i in range(n):
	print result[i]/math.pi/2, 
print

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import cmath

#def angle(center, left, right):
#	bunshi = (left[0] - center[0]) * (right[0] - center[0]) + (left[1] - center[1]) * (right[1] - center[1]) ** 2
#	bunbo = math.sqrt(((left[0] - center[0]) ** 2 + (right[0] - center[0]) ** 2) * ((left[1] - center[1]) ** 2 + (right[1] - center[1]) ** 2))
#	theta = bunshi / bunbo
#	return 1 - math.acos(theta) / 2 * (math.pi)

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
# else n == 2:
#     print(0.5)
#     print(0.5)
#     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)])

Submission status: Accepted

Solution code:
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()
# else n == 2:
#     print(0.5)
#     print(0.5)
#     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)])

Submission status: Accepted

Solution code:
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()
# else n == 2:
#     print(0.5)
#     print(0.5)
#     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)])

Submission status: Accepted

Solution code:
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()
# else n == 2:
#     print(0.5)
#     print(0.5)
#     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)])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
import numpy as np
# import scipy

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

Submission status: Accepted

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

Submission status: Accepted

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