Friday, September 2, 2011

Finding the shortest distance connecting 3 points

I came across another interesting problem, THREETW1 in spoj, thanks to hwk . Here we need to calculate the co-ordinates of the point which connects 3 points in shortest path.
For this problem we need to find the Fermat point . We first calculate the barycenter of this point from the sides of the triangle and then represent it in cartesian form.
This problem has application in finding the point where 3 points would be linked most efficiently , specially in cable wires and telephones.
Happy coding!!

No comments:

Post a Comment