Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Convex Hull by UFO665
def coeffs(x1, y1, x2, y2):
a = y2 - y1
b = x1 - x2
c = -x1 * a - y1 * b
return a, b, c
def distance(x1, y1, x2, y2):
return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
def checkio(data):
lstSorted = sorted(data)
x, y = lstSorted.pop(0)
lstRes = [data.index([x, y])]
for i in range(len(lstSorted)):
lstTemp = []
for point in lstSorted:
a, b, c = coeffs(x, y, *point)
if all(a * p[0] + b * p[1] + c >= 0 for p in data):
lstTemp.append(point)
if lstTemp:
point = min(lstTemp, key=lambda p: distance(x, y, *p))
lstSorted.remove(point)
lstRes.append(data.index(point))
x, y = point
return lstRes
Feb. 28, 2016
