Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Black Holes by martin_b
from itertools import combinations
from operator import itemgetter
from math import pi, asin
def checkio(holes):
def intersection(r1, r2, d):
# computes the right intersection point of circles with equations
# x^2+y^2=r1^2, x^2+(y-d)^2=r2^2
# combine them and eliminating y to get the final equation
x_sq = r2**2 - (r2**2 - r1**2 + d**2)**2 / (4 * d**2)
y_sq = r1**2 - x_sq
return x_sq**.5, y_sq**.5
while True:
# all combinations of black holes, sorted by their distance and x position
hole_pairs = []
for h in combinations(holes, 2):
(h1x, h1y, _), (h2x, h2y, _) = h
hole_pairs.append(
(abs(complex(h1x, h1y) - complex(h2x, h2y)), sorted(h)))
hole_pairs.sort()
for (d, hp) in hole_pairs:
# the bigger black hole is always h1
(h1, h2) = sorted(hp, key=itemgetter(2), reverse=True)
(x1, y1, r1), (_, _, r2) = h1, h2
s1, s2 = pi * r1**2, pi * r2**2
# holes intersect and their surface area fulfills mission condition
if d < r1 + r2 and s1 / s2 >= 1.2:
if d < r1 - r2:
# smaller hole is completely within the bigger one
a = s2
else:
# area of the "half-lens" is the area of circular segment minus
# the area of triangle from center to intersection point
x, y = intersection(r1, r2, d)
a1 = asin(x / r1) * s1 / pi - x * y
a2 = asin(x / r2) * s2 / pi - x * abs(d - y)
# intersection area is sum of the two "half-lens"
# or area of bigger "half-lens" and complement of area of smaller
# "half-lens" if the smaller circle is more than half inside the bigger
a = a1 + a2 if y < d else a1 + s2 - a2
if a / s2 >= .55:
# intersection area fulfills mission condition
# merge the holes and repeat process from the beginning
holes[holes.index(h1)] = (x1, y1, ((s1 + s2) / pi)**.5)
del holes[holes.index(h2)]
break
else:
# no merge - break the loop
break
return holes
April 13, 2016
Comments:
