Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Black Holes by Bronepoezd
import math
def absorb( first, second ):
"""
True if first absorbs second
"""
d = dist( first, second )
r, R = first[ 2 ], second[ 2 ]
if d >= r + R:
return False
S1, S2 = math.pi * r * r, math.pi * R * R
if S1 < 1.2 * S2:
return False
if ( abs( d ) < 1e-9 ) or ( r >= d + R ):
return r >= d + R
#may be it is unnecessary
if ( R >= d + r ):
return False
#http://mathworld.wolfram.com/Circle-CircleIntersection.html
S = r * r * math.acos( ( d * d + r * r - R * R ) / ( 2 * d * r ) )
S += R * R * math.acos( ( d * d + R * R - r * r ) / ( 2 * d * R ) )
S -= 0.5 * ( ( -d + r + R ) * ( d - r + R ) * ( d + r - R ) * ( d + r + R )) ** 0.5
if ( S < 0.55 * min( S1, S2 ) ):
return False
return True
def dist( first, second ):
"""
Distance between centers
"""
return ( ( first[ 0 ] - second[ 0 ] ) ** 2.0 + ( first[ 1 ] - second[ 1 ] ) ** 2.0) ** 0.5
def checkio(data):
data = [ list( x ) for x in data ]
removed = [False] * len(data)
data = list( enumerate( data ) )
while 1:
ans = []
for x in data:
if not removed[ x[ 0 ] ]:
for y in data:
if (not removed[ y[ 0 ] ] ) and ( x[ 0 ] != y[ 0 ] ) and absorb( x[ 1 ], y[ 1 ] ):
ans.append( ( x, y, dist( x[ 1 ], y[ 1 ] ) ) )
if not ans:
break
ans.sort( key = lambda x: x[ 2 ] )
first = ans[ 0 ][ 0 ]
second = ans[ 0 ][ 1 ]
removed[ second[ 0 ] ] = True
data[ first[ 0 ] ][ 1 ][ 2 ] = ( first[ 1 ][ 2 ] ** 2.0 + second[ 1 ][ 2 ] ** 2.0 ) ** 0.5
return [ ( x[ 1 ][ 0 ], x[ 1 ][ 1 ], round( x[ 1 ][ 2 ], 2 ) ) for x in data if not removed[ x[ 0 ]]]
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
def checker(user_ans, right_ans):
if not isinstance(user_ans, (list, tuple)) or \
any(not isinstance(line, (list, tuple)) for line in user_ans):
return False
if any(not isinstance(x, (float, int)) for l in user_ans for x in l):
return False
precision = 0.01
return all(abs(right_coord - user_coord) <= precision
for right_line, user_line in zip(right_ans, user_ans)
for right_coord, user_coord in zip(right_line, user_line))
assert checker(checkio([(2, 4, 2), (3, 9, 3)]), [(2, 4, 2), (3, 9, 3)])
assert checker(checkio([(0, 0, 2), (-1, 0, 2)]), [(0, 0, 2), (-1, 0, 2)])
assert checker(checkio([(4, 3, 2), (2.5, 3.5, 1.4)]), [(4, 3, 2.44)])
assert checker(checkio([(3, 3, 3), (2, 2, 1), (3, 5, 1.5)]), [(3, 3, 3.5)])
Oct. 21, 2015
