Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Convex Hull by TovarischZhukov
def rotate(a,b,c):
return (b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0])
def checkio(data):
retval=[]
minx=min(data, key=lambda x:x[0])[0]
a=start=min([val for val in data if val[0]==minx], key=lambda x:x[1])
while start!=a or not retval:
bdata=data[:]; bdata.remove(a);tmp=[]
for b in bdata:
cdata=bdata[:]
cdata.remove(b)
flag=True
for c in cdata:
if rotate(a,b,c)>0: flag=False
if flag: tmp.append(b)
b=min([(((b[0]-a[0])**2+(b[1]-a[1])**2)**.5,b)for b in tmp], key=lambda x:x[0])[1]
retval.append(a); a=b
return [i for el in retval for i,val in enumerate(data) if val==el]
Feb. 5, 2016
