distance between two points, a b = SQRT[ (xa-xb)^2 + (ya-
yb)^2) ]
Define d = the above distance squared = (xa-xb)^2 + (ya-yb)^2)
d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2
d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2
d = ( xa^2 + xb^2 + ya^2 + yb^2 ) - 2*(
@all
i think all the above approaches are greedy..
we need dynamic solution to this problem..
On Sat, Feb 13, 2010 at 11:42 AM, vikrant singh vikrantsing...@gmail.comwrote:
@sachin : the problem is bit more complex , consider N be 2 , and
coordinates be (-2,0) (0,0) (1,0) (3,0). your
I am thinkin like.. make a completely connected graph.. (connect all
2N points to each other)... then delete connections starting with ones
with max distance between them... this should give the desired result
On Feb 11, 11:20 pm, GentLeBoY vikrantsing...@gmail.com wrote:
given 2N points in a
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
@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 sachin_mi...@yahoo.co.in wrote:
We can make a spanning tree for these 2N points
