NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
195 . 實驗報告
TopCoder
Tags
Description
TDD 正在練習物理實驗，為此，他做了 $N$ 組被描述成數值對的樣例，並將他們都描繪在一張二維的表格上。
基本上根據理論，實驗出來的數據應該會是線性相關的，也就是說，在最理想的情況下，會存在一條線可以經過 TDD 實驗出來的所有 $N$ 個二維點。但凡實驗必有誤差，TDD 實驗得到的數據實際上很難用簡單的一條直線貫穿過所有點。
為了交出完美的實驗報告，TDD 決定把每個點都畫得大一點，他打算找到一個最小的半徑 $r$，使得他能夠將每個點都畫成一個半徑 $r$ 這麼大的圓後，就可以找到一條直線貫穿過所有的點（只要線有碰到圓，就算貫穿）。
你可以幫 TDD 找到這個最小的 $r$ 嗎？
Input Format
輸入首行有一個正整數 $N$，代表點的數量。
接下來 $N$ 行，第 $i$ 行兩個整數 $x_i, y_i$，代表第 $i$ 個點的座標。
- $2\le N\le 3\times 10^ 5$
- $0\le x_i, y_i\le 10^ 9$
- 沒有兩個點的座標一樣
Output Format
輸出一個實數，代表每個點的半徑至少要畫多大才能有一條線貫穿過所有的點。如果所有點共線，輸出 $0$ 即可。
由於答案可能是浮點數，因此只要你輸出的答案滿足相對或絕對誤差不超過 $10^ {-9}$ 皆視為正確。更嚴謹的說，假設 $a$ 是正確答案且 $b$ 是你的答案，如果符合 $\frac{|a-b|}{\max(|a|, |b|, 1)}\le 10^ {-9}$ 就會視為正確。
Sample Input 1
4
1 1
2 3
3 2
4 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
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 |