Nature Reserve

题意翻译

原文翻译: 有一片森林,生活着许多珍稀动物,其中每个动物i都有其巢穴,位置在(x_i,y_i)。为了保护他们,现决定在此地建立自然保护区。 自然保护区的形状为圆形,其中必须包括所有巢穴。 不仅如此,由于有一条河笔直的穿过森林,而动物都喜欢在这条河里喝水,所以自然保护区需要与这条河有公共点。 又因为这条河又是一条航线的一部分,所以自然保护区不能和这条河有两个及以上的公共点。 为了方便计算,河的位置设为y=0 求自然保护区的最小半径(与答案误差不超过10^-6即可)(如果不存在符合条件的答案,输出-1) 简洁翻译: 有N个点,求与y=0相切的,包含这N个点的最小圆的半径

题目描述

There is a forest that we model as a plane and live $ n $ rare animals. Animal number $ i $ has its lair in the point $ (x_{i}, y_{i}) $ . In order to protect them, a decision to build a nature reserve has been made. The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river. For convenience, scientists have made a transformation of coordinates so that the river is defined by $ y = 0 $ . Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of animals. Each of the next $ n $ lines contains two integers $ x_{i} $ , $ y_{i} $ ( $ -10^7 \le x_{i}, y_{i} \le 10^7 $ ) — the coordinates of the $ i $ -th animal's lair. It is guaranteed that $ y_{i} \neq 0 $ . No two lairs coincide.

输出格式


If the reserve cannot be built, print $ -1 $ . Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is considered correct if $ \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6} $ .

输入输出样例

输入样例 #1

1
0 1

输出样例 #1

0.5

输入样例 #2

3
0 1
0 2
0 -3

输出样例 #2

-1

输入样例 #3

2
0 1
1 1

输出样例 #3

0.625

说明

In the first sample it is optimal to build the reserve with the radius equal to $ 0.5 $ and the center in $ (0,\ 0.5) $ . In the second sample it is impossible to build a reserve. In the third sample it is optimal to build the reserve with the radius equal to $ \frac{5}{8} $ and the center in $ (\frac{1}{2},\ \frac{5}{8}) $ .