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()
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
