#The smallest circles
Challenge
This is a variant of the smallest-circle problem, but instead of one circle, you get three. Given a list of coordinates, output three circles such that the following conditions are met:
- Each input coordinate must be located inside or on the perimeter of a circle.
- The sum of the radii of all three circles must be minimal.
- The coordinates and radii of all three circles must be non-negative integers.
You must place all three circles. You may place overlapping circles. A circle with a radius of zero that is directly on top of an input coordinate is considered to be covering that input coordinate.
Input
A list containing between 1 and 1000 pairs of integers, inclusive. Each pair of integers represents an xy-coordinate. Use whatever input format you want to use.
For example, the input...
1,1;1,2;2,2;3,3
... can be drawn like this:
Output
A list of three integer triples. Each triple contains an x coordinate, followed by a y coordinate, followed by a radius. The triples, and the integers within each triple, must be distinguishable from one another. Otherwise, the output format is not important.
Example:
1,1,1;2,2,1;3,3,2
Given this example output, circles would be drawn at (1,1), (2,2), and (3,3). The first two circles would have a radius of 1, and the third would have a radius of 2. The sum of the radii would be 4.
Test case explained
Given the input...
1,1;1,2;2,2;3,3
... you could output...
1,2,1;3,3,0;0,0,0
... or you could output...
1/2/1
3/3/0
0/0/0
The radii sums to 1, and since it is not possible to draw three circles whose radii sum to less than 1 that encompass or touch all four points, this is the correct answer.