There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting
place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time. eg: (x,y) can be reached from (x-1,y+1) in a single unit of time. Find a common meeting place which minimizes the sum of the travel times of all the
persons.
这个题目可以参考之前做的加油站问题,只是一维简化版本
有n个加油站,选择中间的那个加油站,作为总加油站,其他加油站到它的距离最短
可以先把所有的点映射到x轴,找到一个点位于所有点的中位数位置
再把所有的点映射到Y轴,找到一个点位于所有点的中位数位置
这两条线的交点就是meeting place
struct POS { int x; int y; }; bool CompX(POS a, POS b) { return a.x < b.x; } bool CompY(POS a, POS b) { return a.y < b.y; } POS FindMeetingPlace(POS a[], int n) { assert(a && n>0); POS pos; sort(a, a+n, CompX); pos.x = a[n/2].x; sort(a, a+n, CompY); pos.y = a[n/2].y; return pos; }