1
Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.
Distance is measured in the following manner.
For a point (x,y) all 8 adjacent points have distance 1.
(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)
EDIT
More clearer explanation.
A function foo is defined as
foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))
Find a point x such that sum([foo(x,y) for y in list_of_points]) is minimum.
Example
Input:
0 1
2 5
3 1
4 0
Output
3 1
Eg: Distance between (4,5) and 6,7) is 2.
This can be done in O(n^2) time, by checking the sum of each pair. Is there any better algorithm to do it?
I don't understand how the diagonal distances are the same as the perpendicular distances. Also, I'm not sure I understand: are you you asking for the average of the n points? – Griffin – 2011-08-14T20:12:37.037
Edited the question – Greyhound – 2011-08-14T20:20:39.307
@griffin he means chessboard distance
– ratchet freak – 2011-08-14T21:57:13.347Can we assume the points are distinct? Having two points in the same place would give it more weight. – Joey Adams – 2011-08-15T01:17:41.613
1This isn't really a puzzle - wouldn't it belong to SO? – user unknown – 2011-08-15T04:03:21.510
1
Crossposting: http://stackoverflow.com/q/7059500/312172 (with python-tag, there)
– user unknown – 2011-08-15T04:06:58.3201@user unknown: How do you define "puzzle"? For me, the puzzle is finding the more efficient algorithm, and I'm having fun working it out. – Joey Adams – 2011-08-15T10:11:07.813
@Greyhound: Welcome to StackExchange! Please don't cross-post; pick one site and post it there. If it's deemed off-topic, it will hopefully be migrated. See "Is cross-posting a question on multiple Stack Exchange sites permitted if the question is on-topic for each site?"
– Joey Adams – 2011-08-15T10:14:16.637Which one should I pick? For example, which site should I pick,if its Algorithm or Combinatorics related problem. – Greyhound – 2011-08-15T12:03:58.190
@Greyhound: If it is language agnostic, and you do the work to make a competition out of it: PPCG. To post it here, you need to have a metric, by which you decide which solution is best. In most cases: shortest solution. But you would need to clarify, whether to solve an specific example, or take input from a file/system in/program parameters. – user unknown – 2011-08-15T16:19:46.073
Btw.: I somehow overseen your 'is there a better algo than O(n^2)'. Now I deleted my answer, which was 0(n^2). – user unknown – 2011-08-15T16:23:19.950