Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for Wild Dogs by Merzix
def wild_dogs(coords):
dogs_count = len(coords)
if dogs_count < 2:
return 0
lst = [] # [(distance_to_point, dogs_on_line), ...]
for i in range(dogs_count - 1):
x1, y1 = coords[i]
x2, y2 = coords[i+1]
a, b, c = (1, 0, x1) if x1==x2 else ((y2-y1)/(x2-x1), 1, (x2*y1 - x1*y2)/(x2-x1))
max_dogs_on_line = dogs_on_line = 2
for x3,y3 in coords[i+2:]:
dogs_on_line += b*y3 == a*x3 + c
max_dogs = dogs_on_line if dogs_on_line > max_dogs_on_line else max_dogs_on_line
lst.append((round(abs(c)/((a*a + b*b)**0.5), 2), dogs_on_line))
return min(abs(i[0]) for i in lst if i[1] == max_dogs_on_line)
Sept. 13, 2018
Comments:
