Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Hesse solution in Clear category for Wild Dogs by HeNeArKr
import math
from collections import defaultdict
def hesse_normal(pt0, pt1):
""" Return r, theta values of Hesse normal form of line representation
r = x cos(theta) + y sin(theta)
Uniquely identifies each line by vector from origin that is
perpendicular to the line.
"""
# Line1 defined by two points (x0, y0), (x1, y1) has form
# (y-y0)(x1-x0) = (y1-y0)(x-x0)
# Line2 passes through (0, 0). Line2 is perpendicular to line1 with
# slope m1, therefore has slope m2 = -1/m1 and form
# y(y1-y0) = x(x0-x1)
# (x, y) is intersection of line1 and line2
c = (pt0[0]*pt1[1]-pt1[0]*pt0[1])/((pt1[0]-pt0[0])**2+(pt1[1]-pt0[1])**2)
x = (pt1[1]-pt0[1])*c
y = (pt0[0]-pt1[0])*c
# Arbitrarily rounded to 5 decimal points for convenience
return (round(math.hypot(x, y), 5), round(math.atan2(y, x), 5)) # r, theta
def wild_dogs(coords):
""" Return shortest distance to line that includes the largest number of
wild dogs in coords.
"""
lines = defaultdict(int)
for i in range(len(coords)-1):
for j in range(i+1, len(coords)):
lines[hesse_normal(coords[i], coords[j])] += 1
biggest = max(lines.values())
dist = min(hesse[0] for hesse, num in lines.items() if num == biggest)
return int(dist) if int(dist) == dist else round(dist, 2)
Sept. 10, 2018