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..
Problem is:
<div>Meeting Point (50 Points)</div> <div> </div>
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.
Input Format: N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
Output Format: M M = min sum of all travel times;
Constraints: 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;
Input #00:
4
0 1
2 5
3 1
4 0
Output #00:
8
Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.
ashok2009cse
Member
173 Points
123 Posts
need solution to this problem in c#- help
Mar 07, 2012 11:13 AM|LINK
hi all,
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..
Problem is:
<div>Meeting Point (50 Points)</div> <div> </div>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.
Input Format:
N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
Output Format:
M M = min sum of all travel times;
Constraints:
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;