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
##############################################
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))
circs[-1].idx = i
union = union_shapes([], circs)
asum = sum(t2-t1 for _,t1,t2 in union)
ans = 0
for i in range(n):
if any(circs[i] == circs[j] for j in range(n) if i != j):
ans+= 1; continue
if any(C.idx == i for C,_,_ in union): continue
unoi = union_shapes([], circs[:i] + circs[i+1:])
asumnoi = sum(t2-t1 for _,t1,t2 in unoi)
ans+= asumnoi < asum+(1e-9)
print(ans)
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1492 ms |
29912 KB |
Output is correct |
| 2 |
Incorrect |
688 ms |
28560 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
