Use median, it solves the problem I think.
Thanks,
Sathaiah
On Thu, Jun 24, 2010 at 12:21 AM, Dave <dave_and_da...@juno.com> wrote:
> Let the given points be x_i, i = 1, 2, ..., n. For any point x on the
> line, let
> f(x) = sum_{i=1}^n | x - x_i |.
> Then, from calculus, we know that f(x) attains its extreme point at a
> point where its derivative is zero or undefined. Because of the
> absolute value signs, the derivative is undefined at the x_i. Since
> f(x) is linear between adjacent x_i, it suffices to check only f(x_i)
> in search of the minimum. As you proceed toward the right from the
> leftmost x_i, the function decreases as long as there are more x_i to
> the right of x than to the left, and increases whenever there are more
> x_i to the left than to the right. Hence, if N is odd, the minimum
> occurs at the median of the {x_i}. If N is even, the post office can
> be anywhere in the center interval.
>
> Dave
>
> On Jun 23, 7:18 am, amit <amitjaspal...@gmail.com> wrote:
> > There are N points on a LINE. U neeed to place a post office such that
> > its total distance from each of the N points is minimised.
> >
> > The post office need not necessarily be on one of the N Points.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
