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

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.

code-golf math geometry (maybe parsing too)

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:

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.

code-golf math geometry (maybe parsing too)

#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 is minimal.

You must place all three circles. You may place overlapping circles. Each radius must be non-negative (zero is non-negative). 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.

code-golf math geometry (maybe parsing too)

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

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.

code-golf math geometry (maybe parsing too)

#The smallest circles

Write a program that, given a list of xy-coordinates, outputs circles that completely enclose those coordinates.

Input

A list containing between 1 and 1000 pairs of integers. Each pair of integers represents an xy-coordinate. The input format is not important.

Example:

1,1;1,2;2,2;3,3

Challenge

Given these coordinates, you must place exactly three circles such that the following two conditions are met:

• Every coordinate must be located inside or on the perimeter of a circle
• The sum of the radii of all three circles is minimal

You must place all three circles. Each radius must be non-negative (includes zero). You may place overlapping circles.

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.

Actual Test Case

Given the input...

1,1;1,2;2,2;3,3

... you could output...

2,2,2;0,0,0;0,0,0

... or you could output...

1/2/1
3/3/1
0/0/0

The radii of both answers sum of 2, and since it is not possible to draw a circle of radius smaller than 2 that encompasses all four points, either answer is valid.

code-golf math geometry (maybe parsing too)

#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 is minimal.

You must place all three circles. You may place overlapping circles. Each radius must be non-negative (zero is non-negative). 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.

code-golf math geometry (maybe parsing too)