Get Help:Ask a Question in our Forums|Report a Bug|More Help Resources
Mar 07, 2012 11:13 AM|LINK
i came accross thisproblem from one web page, i have tried my best to resolve. i couldn't. i think i am lacking in the logic. can any one solve and tell me the logic with source code..
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 minimises the sum of the travel times of all the persons.
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
M M = min sum of all travel times;
N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109
HINT: Please use long long 64-bit integers;
Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.