TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

69.2% (9/13)

Tags

Description

TDD 正在練習物理實驗,為此,他做了 N 組被描述成數值對的樣例,並將他們都描繪在一張二維的表格上。

基本上根據理論,實驗出來的數據應該會是線性相關的,也就是說,在最理想的情況下,會存在一條線可以經過 TDD 實驗出來的所有 N 個二維點。但凡實驗必有誤差,TDD 實驗得到的數據實際上很難用簡單的一條直線貫穿過所有點。

為了交出完美的實驗報告,TDD 決定把每個點都畫得大一點,他打算找到一個最小的半徑 r,使得他能夠將每個點都畫成一個半徑 r 這麼大的圓後,就可以找到一條直線貫穿過所有的點(只要線有碰到圓,就算貫穿)。

你可以幫 TDD 找到這個最小的 r 嗎?

Input Format

輸入首行有一個正整數 N,代表點的數量。

接下來 N 行,第 i 行兩個整數 xi,yi,代表第 i 個點的座標。

  • 2N3×105
  • 0xi,yi109
  • 沒有兩個點的座標一樣

Output Format

輸出一個實數,代表每個點的半徑至少要畫多大才能有一條線貫穿過所有的點。如果所有點共線,輸出 0 即可。

由於答案可能是浮點數,因此只要你輸出的答案滿足相對或絕對誤差不超過 109 皆視為正確。更嚴謹的說,假設 a 是正確答案且 b 是你的答案,如果符合 |ab|max(|a|,|b|,1)109 就會視為正確。

Sample Input 1

4
1 1
2 3
3 2
4 4

Sample Output 1

0.670820393249937

Sample Input 2

4
1 3
2 4
3 5
4 6

Sample Output 2

0.000000000000000

Hints

Problem Source

IOICamp 2022 Day5 pJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2