Today, I tried to solve a problem like this:
- Given $$$n$$$ convex hull, convex hull $$$i$$$ have size $$$m_i$$$, begin, you started in convex hull number $$$1$$$, then, with a operation, you can do:
Teleport to any points in current convex hull (with cost $$$0$$$), then use a balloon to fly to a point in another convex hull with cost is Euclid's distance between that two points.
Teleport to any points in any convex hull that you have visited with cost $$$0$$$.
Find minium cost to visit all the convex hull.
Input: $$$1\leq n, m_i\leq 200$$$.
My main idea to this problem is, find all edge between two convex hulls (easy to see, cost of that edge is closest distance between that two convex hulls, let call is $$$X$$$), then build the MST, answer is sum of the all cost of edge in MST.
But, I just can find the $$$X$$$ of two convex hulls in $$$O(m^2)$$$ and can't do better, can anyone help me with this. Thank you and sorry for my bad English.
jeroenodb
The distance between two polygons $$$P$$$, $$$Q$$$, is the minimum norm of any point in the minkowski sum $$$P + (-Q)$$$.
For convex polygons you can compute this in linear time, then iterate on each vertex and check its norm; distance to $$$(0,0)$$$.
Edit: actually you also need to check distances to the edges.