Submission #565066

#	Time	Username	Problem	Language	Result	Execution time	Memory
565066		jh05013	색종이 (kriii3_T)	Pypy 3	36 / 109	769 ms	29788 KiB

paper

from math import sin, cos, tan, pi, asin, acos, atan
from functools import cmp_to_key, total_ordering
def sgn(x): return (0<x) - (x<0)
 
## Pnt ##############################################
 
@total_ordering
class Pnt:
    def __init__(_, x, y): _.x,_.y = x,y
    def __repr__(_): return f"({_.x}, {_.y})"
    
    # Basic ops
    def sq(_): return _.x**2 + _.y**2
    def __abs__(_): return (_.x**2 + _.y**2)**.5
    def __le__(_, o): return (_.x, _.y) <= (o.x, o.y)
    
    # Scalar ops
    def __mul__(_, d): return Pnt(d*_.x, d*_.y)
    def __rmul__(_, d): return Pnt(_.x*d, _.y*d)
    def __truediv__(_, d): return Pnt(_.x/d, _.y/d)
    def __floordiv__(_, d): return Pnt(_.x//d, _.y//d)
    
    # Vector ops
    def __eq__(_, q): return _.x==q.x and _.y==q.y
    def __add__(_, q): return Pnt(_.x+q.x, _.y+q.y)
    def __sub__(_, q): return Pnt(_.x-q.x, _.y-q.y)
    
    # Tranformations
    def scale(_, c, factor): return c + (_-c)*factor
    def rot(_, t): return Pnt(_.x*cos(t)-_.y*sin(t), _.x*sin(t)+_.y*cos(t))
    def rotc(_, c, t): return c + (_-c).rot(t)
    def rot90(_): return Pnt(-_.y, _.x) 
O, O10, O01 = Pnt(0, 0), Pnt(1, 0), Pnt(0, 1)
 
# Vector functions
def distsq(p, q): return (p-q).sq()
def dist(p, q): return abs(p-q)
def dot(p, q): return p.x*q.x + p.y*q.y
def cross(p, q): return p.x*q.y - p.y*q.x
def angle(p, q): return acos(max(-1, min(1, dot(p,q)/abs(p)/abs(q))))
 
# Angles
def orient(a, b, c): return cross(b-a, c-a) # >0 ccw
def ccw(a, b, c): return sgn(cross(b-a, c-a)) # 1 ccw
def at_angle(t): return Pnt(cos(t), sin(t))
def angle_change(p, q):
    theta = angle(p, q)
    return theta if orient(p,Pnt(0,0),q)<=0 else 2*pi-theta
def angle_diff(p, q):
    theta = angle(p, q)
    return min(theta, 2*pi-theta)
def angle_change_c(c, p, q):
    return angle_change(p-c, q-c)
def angle_diff_c(c, p, q):
    return angle_diff(p-c, q-c)
 
## Polar sort ##############################################
 
# Sort by angle
def half_p(p): return p.y>0 or (p.y==0 and p.x<0)
@cmp_to_key
def half_cmp(p, q):
    A = (half_p(p), 0, p.sq())
    B = (half_p(q), cross(p,q), q.sq())
    return 0 if A==B else (-1 if A<B else 1)
def polarsort(c, pnts):
    return [x+c for x in sorted([x-c for x in pnts], key=half_cmp)]
 
## Circle ##############################################
 
class Circle:
    def __init__(_, c, r): _.c,_.r = c,r
    def __repr__(_): return f"O{_.c}+{_.r}"
    
    def __eq__(C1, C2): return C1.c == C2.c and C1.r == C2.r
    
    # Circle to point
    def angle_of(_, p): return angle_change_c(_.c, _.c+O10, p)
    def at_angle(_, t): return _.c + at_angle(t)*_.r
    def at_vector(_, v): return _.c + v*_.r/abs(v)
 
def point_in_circle(p, C, strict=False):
    if strict: return distsq(p, C.c) < C.r**2
    return distsq(p, C.c) <= C.r**2
 
# TODO make it corner-case-friendly
def solve_quadratic(a, b, c, l, r):
    D = b**2 - 4*a*c
    if D < 0: L = []
    elif D == 0: L = [-b/(2*a)]
    else: L = [(-b-D**.5)/(2*a), (-b+D**.5)/(2*a)]
    return [x for x in L if l <= x <= r]
def circle_seg_inters(C, a, b):
    v = b-a; f = a-C.c
    X = solve_quadratic(dot(v,v), 2*dot(f,v), dot(f,f)-C.r**2, 0, 1)
    return [a+t*v for t in X]
 
def circle_circle_inters(C1, C2, strict = False):
    assert C1 != C2 # TODO handle this case
    dsq = distsq(C1.c, C2.c)
    if dsq > (C1.r + C2.r)**2 or dsq < (C1.r - C2.r)**2: return []
    if dsq == (C1.r + C2.r)**2 or dsq == (C1.r - C2.r)**2:
        return [] if strict else [C1.at_vector(C2.c - C1.c)]
    v = C2.c - C1.c
    pd = (dsq + C1.r**2 - C2.r**2)/2
    p = C1.c + v*pd/dsq
    h = v.rot90() * ((C1.r**2 - pd**2/dsq)/dsq)**.5
    return [p-h, p+h]
 
## Area ops ##############################################
 
def union_shapes(segs, circs):
    circs = [circs[i] for i in range(len(circs)) if\
             not any(circs[i] == circs[j] for j in range(i+1, len(circs)))]
    ns = len(segs)
    nc = len(circs)
    frags = []
    assert not ns # TODO handle segs
    for i in range(nc):
        C = circs[i]
        inters = []
        # TODO handle segs
        for j in range(nc):
            if i == j: continue
            inters.extend(circle_circle_inters(C, circs[j]))
        inters = polarsort(C.c, inters)
        inters = [C.angle_of(p) for p in inters]
        if not inters: inters.append(0)
        for ai in range(len(inters)):
            t1, t2 = inters[ai-1], inters[ai]
            if t1 > t2: t2+= 2*pi
            p = C.at_angle((t1+t2)/2)
            if not any(point_in_circle(p, circs[j]) for j in range(nc) if i != j):
                frags.append((C, t1, t2))
    return frags

def green_seg(a, b):
    v = b-a
    return cross(a, v)/2

def green_circle(C, tl, tr):
    x, y, r = C.c.x, C.c.y, C.r
    a = r**2 * (tr-tl)
    b = x*r * (sin(tr)-sin(tl))
    c = y*r * (cos(tl)-cos(tr))
    return (a+b+c)/2

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

from itertools import accumulate
MIS = lambda: map(int,input().split())
 
n = int(input())
circs = []
for i in range(n):
    _,x,y,r = MIS()
    circs.append(Circle(Pnt(x,y), r))

ans = [[0]*n for i in range(n)]
for i in range(n):
    C = circs[i]
    
    # find intersections
    inters = []
    for j in range(n):
        if i == j: continue
        if j > i and C == circs[j]: break
        if C == circs[j]: continue
        for p in circle_circle_inters(C, circs[j]): inters.append(C.angle_of(p))
    if not inters: inters.append(0)
    inters = sorted(set(inters))
    
    # find when each fragment is on the boundary
    for ai in range(len(inters)):
        t1 = inters[ai-1]; t2 = inters[ai]
        if t1 >= t2: t2+= 2*pi
        mp = C.at_angle((t1+t2)/2)
        frag = green_circle(C, t1, t2)
        for jl in range(i-1, -2, -1):
            if jl == -1: break
            if C != circs[jl] and point_in_circle(mp, circs[jl]): break
        for jr in range(i+1, n+1):
            if jr == n: break
            if C == circs[jr]: break
            if point_in_circle(mp, circs[jr]): break
        jl+= 1; jr-= 1
        # ans[jl..i][i..jr]+= frag
        #print(C, t1, t2, "area", frag, "--", jl, jr)
        for l in range(jl, i+1):
            ans[l][i]+= frag
            if jr != n-1: ans[l][jr+1]-= frag
for i in range(n): ans[i] = list(accumulate(ans[i]))

#for row in ans: print(row)
for i in range(n):
    for j in range(i+1):
        a_with = ans[j][i]
        a_without = ans[j+1][i] if j != i else 0
        a = a_with - a_without
        print(a, end=' ')
    print()

'''
3
2 0 0 1
2 1 2 3
2 0 0 1
'''

• Subtask 1: 36 / 36
• Subtask 2: 0 / 73