Villages lie along a single straight road. Village i is at kilometre position along the road and has people inhabitants. The council will build one clinic at a whole-number kilometre mark, and everyone will travel to it along the road. The cost of a site is the total distance travelled if every inhabitant makes one trip: the sum over the villages of people * |site - position|.
Write best_site(villages) where villages is a list of (position, people) pairs in no particular order, and return the tuple (site, cost) for a site with the smallest cost. If several sites share the smallest cost, return the one nearest the start of the road (the smallest kilometre mark).
Examples
Input: villages = [(2, 10), (5, 1), (9, 1)]
Output: (2, 10)
Explanation: at kilometre 2 the cost is 10*0 + 1*3 + 1*7 = 10. At kilometre 5 it would be
10*3 + 0 + 1*4 = 34: the big village pulls the site to itself.
Input: villages = [(0, 3), (10, 3)]
Output: (0, 30)
Explanation: every site from 0 to 10 costs 30; the smallest is 0.
Input: villages = [(12, 4), (3, 2), (7, 1), (20, 2)]
Output: (12, 39)
Explanation: 2*9 + 1*5 + 4*0 + 2*8 = 39.
Constraints
1 <= len(villages) <= 10**50 <= position <= 10**9, and several villages may share a position0 <= people <= 10**4, and at least one village haspeople >= 1
Goals
- Find the point that makes the total distance travelled as small as possible
- Weight every village by how many people live there
- Replace a slow try-every-position search with one pass over the sorted villages