@sachin : the problem is bit more complex , consider N be 2 , and coordinates be (-2,0) (0,0) (1,0) (3,0). your solution( min value=1+5=6) wont give the right answer(2+2=4).
On Sat, Feb 13, 2010 at 6:07 PM, sachin <[email protected]> wrote: > We can make a spanning tree for these 2N points and then find the > minimum spanning tree > keeping in mind that a node can only be considered in one edge and not > more than once. > This will give you the minimum total sum of all the pairs. > You can use kruskal's min spanning tree algorithm to find the minimum > spanning tree because > kruskal's method works by finding the least cost edges & then > proceeding towards the max cost edges. > I hope it solves your problem. > > Regards, > Sachin > > > On Feb 12, 9:20 am, GentLeBoY <[email protected]> wrote: > > given 2N points in a plane. Pair up to obtain N distinct pairs such > > that total sum of paired distances is minimum. > > N can be atmost 50. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
