Submission #660296

# Submission time Handle Problem Language Result Execution time Memory
660296 2022-11-21T14:01:04 Z riyuna Lonely mdic (kriii1_L) PyPy 3
0 / 1
67 ms 20260 KB
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

File "L.py", line 73
    else:
    ^
SyntaxError: invalid syntax
# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 20260 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -