Submission #660289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660289	2022-11-21T13:16:54 Z	riyuna	Lonely mdic (kriii1_L)	PyPy 3	0 / 1	2000 ms	31864 KB

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 solve():
    n = int(input())
    
    circles = []
    cnt = 0
    
    for i in range(n):
        x, y, r = map(int, input().split())
        
        new_circle = Circle(Point(x, y), r)
        
        circles.append(new_circle)
    
    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()

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	474 ms	28968 KB	Output is correct
2	Correct	175 ms	26448 KB	Output is correct
3	Correct	155 ms	26388 KB	Output is correct
4	Correct	361 ms	27316 KB	Output is correct
5	Correct	820 ms	29676 KB	Output is correct
6	Correct	1018 ms	31104 KB	Output is correct
7	Correct	957 ms	31700 KB	Output is correct
8	Execution timed out	2083 ms	31864 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-