이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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 C == circs[j]: break
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 point_in_circle(mp, circs[jl], True): 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
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 i in range(n):
for j in range(i+1):
a_with = ans[j][i]
a_without = ans[j+1][i] if j != n-1 else 0
a = a_with - a_without
print(a, end=' ')
print()
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
