| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 565066 |
2022-05-20T08:35:19 Z |
jh05013 |
색종이 (kriii3_T) |
PyPy 3 |
|
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 |
- |
