Function aoc::year2018::day06::part2_testable

pub fn part2_testable(input: &Input, max_distance: i32) -> i32

Sweep from top to bottom to find the size of the roughly circular area that is less than a specified maximum distance from all other points.

Finding the center of this circle to act as a starting point is an interesting sub-problem. The two dimensional geometric median that minimizes the Euclidean distance to all other points has no general closed form formula. The centroid is close but not exact as it minimizes the distance squared.

However the Manhattan distance is independent for each axis, so we can instead solve for the one dimensional case. This is the median of each axis. Intuitively this makes sense, as the median has the same number of points on either side, so moving either direction, the increase from half the points is cancelled out by the decrease of the other half of the points.

The algorithm is:

• Find center
• Go upwards from center until top edge of circle reached.
• For each row of circle, find left and right extents
• Add area of row to total, then advance to row below.