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
if c1.rad + ctr_dist <= c2.rad:
c1.deactivate(0, 2 * math.pi)
return
if c2.rad + ctr_dist <= c1.rad:
c2.deactivate(0, 2 * math.pi)
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()
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
342 ms |
27740 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
27080 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
