Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Three Points Circle by Rounin
def distance(a, b): # Actually distance squared
return (b[0]-a[0])*(b[0]-a[0])+(b[1]-a[1])*(b[1]-a[1])
def add(a, b):
return [a[0]+b[0], a[1]+b[1]]
def scale(a, b):
return [a[0]*b, a[1]*b]
def distancetocentre(point, data):
distances = list(map(lambda x: distance(point, x), data))
return abs(distances[0]-distances[1])+abs(distances[1]-distances[2])+abs(distances[2]-distances[0])
def checkio(data):
data = eval('['+data+']')
# Find the midpoint the two most distant points
data = sorted(data, key = lambda x: -distancetocentre(x, data.copy()))
midpoint = scale(add(data[0], data[1]), 0.5)
atob = [data[1][0]-data[0][0], data[1][1]-data[0][1]] # Make a vector between them
# Make a vector that points away from both, and towards the center of all three
vector = [-atob[1], atob[0]]
# Scale the vector until it poins at the exact centre
minscalar = -1
maxscalar = 1
while distancetocentre(add(midpoint, scale(vector, maxscalar*2)), data) < distancetocentre(add(midpoint, scale(vector, maxscalar)), data):
maxscalar *= 2
while distancetocentre(add(midpoint, scale(vector, minscalar*2)), data) < distancetocentre(add(midpoint, scale(vector, minscalar)), data):
minscalar *= 2
bestdist = distancetocentre(add(midpoint, scale(vector, 0)), data)
bestscalar = 0
for i in range(10001):
scalar = minscalar + ((maxscalar-minscalar)*(i/10000))
newdist = distancetocentre(add(midpoint, scale(vector, scalar)), data)
if newdist <= bestdist:
bestdist = newdist
bestscalar = scalar
centerpoint = add(midpoint, scale(vector, bestscalar))
centerpoint.append(distance(data[2], centerpoint)**0.5)
centerpoint = list(map(lambda x: round(x*100)/100, centerpoint)) # Round off to two digits
centerpoint = list(map(lambda x: int(x) if (x % 1) == 0.0 else x, centerpoint)) # Round to integer
return '(x-'+str(centerpoint[0])+')^2'+'+(y-'+str(centerpoint[1])+')^2='+str(centerpoint[2])+'^2'
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio("(2,2),(6,2),(2,6)") == "(x-4)^2+(y-4)^2=2.83^2"
assert checkio("(3,7),(6,9),(9,7)") == "(x-6)^2+(y-5.75)^2=3.25^2"
July 29, 2017