Editorial for Another Contest 3 Problem 2 - Camelot


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

If we rotate the plane by 45 degrees, we're solving the same problem of finding a point that minimizes the sum of the distances to that point, except the distance metric is Manhattan distance, where dimensions are independent. In the one-dimensional variant where the distance metric is Manhattan distance, the point that minimizes the distance is the median of the points.

To rotate the points by 45 degrees, map (x, y) to (x+y, x-y). We can compute the median of the sums and differences to get a candidate point in the original space, but note that the given point might not be a lattice point (this happens when the medians have different parities). Nonetheless, we can try all points in the neighborhood of that point, one of which will be optimal.


Comments

There are no comments at the moment.