Đường Tròn Bao Nhỏ Nhất · canuc80k5725

Cho $n$ điểm phân biệt trên mặt phẳng. Hãy tìm bán kính nhỏ nhất của một đường tròn chứa tất cả các điểm ở bên trong hoặc trên đường tròn. Tâm đường tròn có thể là bất kỳ điểm thực nào.

Input

Dòng đầu chứa $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}, y_{i}$ .

Output

In bán kính nhỏ nhất. Sai số tuyệt đối hoặc tương đối không vượt quá $1 0^{- 6}$ .

Constraints

$2 \leq n \leq 50$ .
$0 \leq x_{i}, y_{i} \leq 1000$ .
Các điểm đôi một khác nhau.

Scoring

Subtask $1$ ( $50$ điểm): $n \leq 10$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

1.414213562373095

Giải thích: Tâm $(1, 1)$ cách cả bốn điểm đúng $2$ , nên bán kính $2$ là đủ; hai đỉnh đối diện cách nhau $22$ , vì vậy không thể dùng bán kính nhỏ hơn.

Ý tưởng: Với tâm (x,y), đặt F(x,y)=max_i((x-x_i)^2+(y-y_i)^2). Mỗi khoảng cách bình phương là hàm lồi, nên maximum của chúng cũng lồi.
Ý tưởng: Khi cố định x, tam phân y trên [0,1000] để tìm giá trị nhỏ nhất. Hàm giá trị sau khi tối ưu một tọa độ vẫn lồi theo x, vì F jointly convex trên miền hình chữ nhật; do đó tiếp tục tam phân ngoài theo x. Có thể giới hạn tâm trong [0,1000]^2, bởi chiếu một tọa độ nằm ngoài về biên gần nhất không tăng khoảng cách tới bất kỳ điểm đầu vào nào. Cuối cùng lấy căn của khoảng cách bình phương lớn nhất. Độ phức tạp O(nI^2), bộ nhớ O(n).