Submission #564176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564176	2022-05-18T16:37:09 Z	jh05013	Lonely mdic (kriii1_L)	PyPy 3	0 / 1	1492 ms	29912 KB

L

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)

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	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	-