Consider N points forming a circle (N is even and is between 1 and 200).
The task is to calculate the minimum cost of linking all 2 points (as pairs) without any lines intersecting.
Each point is given an ID. The cost to link 2 points a and b is (id(a)+id(b))²
Please note: a point can't be part of 2 pairs.
a=1, b=2, c=1, d=2
Here's how I approached the problem:
First we locate the point with the smallest id and the node with the greatest id value. If one is odd and the other is even then we link them. Else, we locate the point with the second biggest id value and we link the located points.
The cost is calculated and saved, and the points are removed from our structure (C++ std::list for example) and the function is called recursively twice, each time with a subset of the current circle, left part and right part (2 new circles)
The base case for the recursive function is returning the square of the sum of 2 points if N=2