Performing at the Center of the World
Time limit2sMemory limit128 MB
Given up to 100 points on a plane, compute the center and radius of the minimum enclosing circle covering all of them.
- Level
Hard8 of 10
- Topics
- Geometry, Math, Brute force
- Solved
- No attempts yet
Problem
A musician is preparing a performance for the fans. To make the performance feel shared with the audience, the concert hall is considered as a circle, and every fan must lie inside the circle or on its boundary.
The positions of N fans are given as plane coordinates (x, y). The musician wants to perform at the center of a circle with the smallest possible radius among all circles that contain every fan.
Write a program that finds the center coordinates and radius of such a smallest circle.
Input
The first line contains N, the number of fans. (1 <= N <= 100)
Each of the next N lines contains the x-coordinate and y-coordinate of one fan. Each coordinate is given with at most six digits after the decimal point and satisfies -600000 <= x, y <= 600000.
Output
Print three numbers on the first line: the x-coordinate of the circle's center, the y-coordinate of the center, and the radius. An absolute or relative error of at most is accepted.