Submission #565066

# Submission time Handle Problem Language Result Execution time Memory
565066 2022-05-20T08:35:19 Z jh05013 색종이 (kriii3_T) PyPy 3
36 / 109
769 ms 29788 KB
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
'''
# Verdict Execution time Memory Grader output
1 Correct 690 ms 29048 KB Output is correct
2 Correct 769 ms 29788 KB Output is correct
3 Correct 679 ms 28812 KB Output is correct
4 Correct 503 ms 29280 KB Output is correct
5 Correct 551 ms 29344 KB Output is correct
6 Correct 615 ms 29192 KB Output is correct
7 Correct 579 ms 29000 KB Output is correct
8 Correct 636 ms 29228 KB Output is correct
9 Correct 468 ms 28844 KB Output is correct
10 Correct 430 ms 28744 KB Output is correct
11 Correct 526 ms 28396 KB Output is correct
12 Correct 378 ms 28076 KB Output is correct
13 Correct 484 ms 28976 KB Output is correct
14 Correct 405 ms 28712 KB Output is correct
15 Correct 474 ms 28316 KB Output is correct
16 Correct 467 ms 28580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 20988 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -