Editorial for Mock CCC '19 Contest 2 S5 - Tudor Takes Pictures of Goats

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.

To rephrase the problem, we need to minimize the number of distinct distances from the given set of points to a point that we can choose.

Assuming $N \ge 2$ ~N \ge 2~, the optimal point clearly lies on the perpendicular bisector between some two points. We can try the midpoint of every pair of points and the intersection of any pair of perpendicular bisectors. There are $\mathcal O(N^4)$ ~\mathcal O(N^4)~ candidate points to consider, for an $\mathcal O(N^5)$ ~\mathcal O(N^5)~ algorithm.

Care should be taken to use exact arithmetic everywhere.

Comments

There are no comments at the moment.