Submission #660680

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660680	2022-11-22T18:47:08 Z	hun3555	Lonely mdic (kriii1_L)	PyPy 3	0 / 1	339 ms	28040 KB

L

from sys import stdin
from math import pi, acos, atan
from copy import deepcopy


input = stdin.readline
err = 1e-7


class Point:
    __slots__ = ('x', 'y')

    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __add__(self, other):
        return Point(self.x+other.x, self.y+other.y)
    
    def __sub__(self, other):
        return Point(self.x-other.x, self.y-other.y) 
    
    def __pow__(self, other):
        return self.x * other.x + self.y * other.y
    
    def __abs__(self):
        return self ** self
    
    def dist(self, other):
        res = self-other
        return abs(res)**0.5


class Circle:
    __slots__ = ('ctr', 'rad', 'on', 'deactive', 'active')

    def __init__(self, ctr: Point, rad):
        self.ctr = ctr
        self.rad = rad
        self.deactive = dict()
        self.on = True
        self.active = []
    
    def deactivate(self, st, ed):
        if st > ed:
            self.deactivate(st, 2 * pi)
            self.deactivate(0, ed)
            return
        
        if st not in self.deactive:
            self.deactive[st] = 1
        else:
            self.deactive[st] += 1
        
        if ed not in self.deactive:
            self.deactive[ed] = -1
        else:
            self.deactive[ed] -= 1
    
    def calculate_active(self):
        self.active = []
        
        bef = 0
        flag = 0
        
        states = sorted(self.deactive.keys())
        
        for state in states:
            val = self.deactive[state]
            
            if flag == 0 and val > 0:
                if state-bef > err:
                    self.active.append(bef)
                    self.active.append(state)
            
            flag += val
            
            if flag == 0 and val < 0:
                bef = state
        
        self.deactive = dict()


def adjust_angle(angle):
    while angle < 0:
        angle += 2 * pi
    while angle > 2 * pi:
        angle -= 2 * pi
    return angle


def circle_intersect(c1: Circle, c2: Circle):
    ctr_dist = c1.ctr.dist(c2.ctr)
    
    if ctr_dist > c1.rad + c2.rad:
        return
    
    angle1 = acos((-c2.rad**2 + c1.rad**2 + ctr_dist**2)/(2 * c1.rad * ctr_dist))
    angle2 = acos((-c1.rad**2 + c2.rad**2 + ctr_dist**2)/(2 * c2.rad * ctr_dist))
    
    dvec = c2.ctr - c1.ctr
    angle = atan(dvec.y / dvec.x) if dvec.x != 0 else (pi / 2 if dvec.y > 0 else 3 * pi / 2)
    if dvec.x < 0:
        angle += pi
    
    angle1_st = adjust_angle(angle - angle1)
    angle1_ed = adjust_angle(angle + angle1)
    
    angle2_st = adjust_angle(pi + angle - angle2)
    angle2_ed = adjust_angle(pi + angle + angle2)
    
    c1.deactivate(angle1_st, angle1_ed)
    c2.deactivate(angle2_st, angle2_ed)


def find_composition(circles):
    for i in range(len(circles)):
        if not circles[i].on:
            continue
        for j in range(i+1, len(circles)):
            if not circles[j].on:
                continue
            circle_intersect(circles[i], circles[j])
    
    for circle in circles:
        circle.calculate_active()


def check_circle_in_circle(circles):
    real = []

    for i in range(len(circles)):
        c1 = circles[i]
        is_real = True
        for j in range(len(circles)):
            if i == j:
                continue
            c2 = circles[j]

            ctr_dist = c1.ctr.dist(c2.ctr)

            if abs(c1.rad + ctr_dist - c2.rad) < err:
                is_real = False
                break
        
        if is_real:
            real.append(c1)
    
    return real


def solve(n, circles):
    circles = check_circle_in_circle(circles)
    cnt = n - len(circles)
    n = len(circles)
    
    total = deepcopy(circles)
    find_composition(total)
    
    for i in range(n):
        if total[i].active:
            continue
        
        circles[i].on = False
        find_composition(circles)
        nonactive = True
        
        for j in range(n):
            if j == i:
                continue
            if total[j].active != circles[j].active:
                nonactive = False
                break
        
        if nonactive:
            cnt += 1
        
        circles[i].on = True
    
    return cnt


def main():
    n = int(input())
    circles = []

    for _ in range(n):
        x, y, r = map(int, input().split())
        circles.append(Circle(Point(x, y), r))
    print(solve(n, circles))


main()

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	339 ms	28040 KB	Output is correct
2	Incorrect	239 ms	27248 KB	Output isn't correct
3	Halted	0 ms	0 KB	-