#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:

 1. Each input coordinate must be located inside or on the perimeter of a circle.
 2. The sum of the radii of all three circles must be minimal.
 3. 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:

[![enter image description here][1]][1]

**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.

----------

[tag:code-golf] [tag:math] [tag:geometry] (maybe [tag:parsing] too)


  [1]: https://i.sstatic.net/ZaikL.png