Submission #660295

#	Time	Username	Problem	Language	Result	Execution time	Memory
660295		riyuna	Lonely mdic (kriii1_L)	Pypy 3	0 / 1	59 ms	20136 KiB

L

    import sys
    import math
    import copy
     
     
    input = sys.stdin.readline
    err = 1e-5
     
     
    class Point:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        
        def __str__(self):
            return f"({self.x}, {self.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 __mul__(self, multiplier):
            return Point(self.x*multiplier, self.y*multiplier)    
        
        def __pow__(self, other):
            return self.x * other.x + self.y * other.y
        
        def __floordiv__(self, other):
            return self.x * other.y - self.y * other.x
        
        def __eq__(self, other):
            return self.x == other.x and self.y == other.y
        
        def __abs__(self):
            return self ** self
        
        def dist(self, other):
            res = self-other
            return abs(res)**0.5
     
     
    class Circle:
        def __init__(self, ctr: Point, rad):
            self.ctr = ctr
            self.rad = rad
            self.active = [[0, 2 * math.pi]]
        
        def __str__(self):
            return f"center {self.ctr}, radius {self.rad}, active {self.active}"
        
        def __eq__(self, other):
            return self.ctr == other.ctr and self.rad == other.rad
        
        def point_in(self, point: Point):
            return self.ctr.dist(point) <= self.rad**2
        
        def intersect(self, other):
            return (self.rad + other.rad)**2 >= self.ctr.dist(other.ctr)
        
        def deactivate(self, st, ed):
            if st > ed:
                self.deactivate(st, 2 * math.pi)
                self.deactivate(0, ed)
                return
            
            new_active = []
            
            for ist, ied in self.active:
                if ied <= st or ed <= ist:
                    new_active.append([ist, ied])
                else:
                    if st - ist > err:
                        new_active.append([ist, st])
                    if ied - ed > err:
                        new_active.append([ed, ied])
            
            self.active = new_active
     
     
    def adjust_angle(angle):
        while angle < 0:
            angle += 2 * math.pi
        while angle > 2 * math.pi:
            angle -= 2 * math.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
        
        if c1.rad + ctr_dist < c2.rad:
            c1.active = []
            return
        
        if c2.rad + ctr_dist < c1.rad:
            c2.active = []
            return
        
        angle1 = math.acos((-c2.rad**2 + c1.rad**2 + ctr_dist**2)/(2 * c1.rad * ctr_dist))
        angle2 = math.acos((-c1.rad**2 + c2.rad**2 + ctr_dist**2)/(2 * c2.rad * ctr_dist))
        
        dvec = c2.ctr - c1.ctr
        angle = math.atan(dvec.y / dvec.x) if dvec.x != 0 else (math.pi / 2 if dvec.y > 0 else 3 * math.pi / 2)
        if dvec.x < 0:
            angle += math.pi
        
        angle1_st = adjust_angle(angle - angle1)
        angle1_ed = adjust_angle(angle + angle1)
        
        angle2_st = adjust_angle(math.pi + angle - angle2)
        angle2_ed = adjust_angle(math.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)):
            for j in range(i+1, len(circles)):
                circle_intersect(circles[i], circles[j])
     
     
    def check_circle_in_circle(circles):
        real = []
     
        for i in range(len(circles)):
            is_real = True
            for j in range(len(circles)):
                if i == j:
                    continue
                c1 = circles[i]
                c2 = circles[j]
     
                ctr_dist = c1.ctr.dist(c2.ctr)
     
                if c1.rad + ctr_dist < c2.rad:
                    is_real = False
                    break
            
            if is_real:
                real.append(c1)
        
        return real
     
     
    def solve():
        n = int(input())
        
        circles = []
        
        for i in range(n):
            x, y, r = map(int, input().split())
            
            new_circle = Circle(Point(x, y), r)
            
            circles.append(new_circle)
        
        circles = check_circle_in_circle(circles)
        cnt = n - len(circles)
        n = len(circles)
        
        total = copy.deepcopy(circles)
        find_composition(total)
        
        for i in range(n):
            if total[i].active:
                continue
            
            part = [copy.deepcopy(circles[j]) for j in range(n) if i != j]
            find_composition(part)
            nonactive = True
            
            for j in range(n-1):
                k = j if j < i else j+1
                
                if total[k].active != part[j].active:
                    nonactive = False
            
            if nonactive:
                cnt += 1
        
        print(cnt)
     
     
    if __name__ == "__main__":
        solve()

Compilation message (stderr)

File "L.py", line 4
    
    ^
SyntaxError: invalid character in identifier

• Subtask 1: 0 / 1