Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Convex Hull by eugene100372
def checkio(data):
def vm(a,b,c):
x1=b[0]-a[0]
x2=c[0]-b[0]
y1=b[1]-a[1]
y2=c[1]-b[1]
return x2*y1-x1*y2
def stack(lst):
res=lst[:2]
for el in lst[2:]:
while len(res)>1 and vm(res[-2],res[-1],el)<0:
res.pop(-1)
res.append(el)
return res[:-1]
m=max(data)
n=min(data)
k=(m[1]-n[1])/(m[0]-n[0])
b=m[1]-k*m[0]
l1=[n]
l2=[]
for el in data:
if el[1] >round(k*el[0]+b):
l1.append(el)
else:
l2.append(el)
return [data.index(cor) for cor in (stack(sorted(l1)+[m])+stack(sorted(l2,reverse=True)))]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio(
[[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]
) == [4, 5, 6, 0, 1, 2, 3], "First example"
assert checkio(
[[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]
) == [1, 0, 6, 3, 5, 2], "Second example"
May 8, 2018
