Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Convex Hull by kurosawa4434
from math import sqrt, degrees, acos
def checkio(data):
def degree_calc(p1, p2, p3):
x1, y1 = p1
x2, y2 = p2
x3, y3 = p3
a = sqrt((abs(x2 - x3))**2 + (abs(y2 - y3))**2)
b = sqrt((abs(x1 - x2))**2 + (abs(y1 - y2))**2)
c = sqrt((abs(x1 - x3))**2 + (abs(y1 - y3))**2)
r = round(degrees(acos((b**2 + c**2 - a**2) / (2 * b * c))))
return r
def search_convex(rest, points, start):
if not rest:
return points
max_deg = []
for i, np in enumerate(rest):
if np == points[-1]:
continue
deg = degree_calc(points[-1], points[-2], np)
dis = abs(np[0] - points[-1][0]) + abs(np[1] - points[-1][1])
if not max_deg or deg > max_deg[1] or deg == max_deg[1] and dis < max_deg[3]:
max_deg = (np, deg, i, dis)
if max_deg[0] == start:
return points
return search_convex(rest[:max_deg[2]] + rest[max_deg[2] + 1:], points + [max_deg[0]], start)
start = sorted(data)[0]
result = search_convex(data, [(start[0], start[1] - 1), start], start)
return [data.index(p) for p in result if p in data]
July 23, 2016
Comments:
