193 . 綠色道路

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

42.9% (9/21)

Tags

ioicamp ioicamp-2022

Description

IOIC 公園希望可以建造一條讓遊客可以自在玩耍的長條道路，為此，IOIC 公園統計了在公園內座落的 $N$ 棵樹，並以二維座標上的 $N$ 個點表示，第 $i$ 棵樹的座標為 $(x_i, y_i)$。此外，沒有兩棵樹落在同樣的地點。

IOIC 公園希望這條長條道路是由兩條可被視為無限長的平行直線所構成的，這兩條直線會將整個平面切成三個區塊，被夾在中間的區塊就是所謂的長條道路，因此 IOIC 公園同時也打算讓他們創建的長條道路上不能有任何樹在道路的嚴格內部（也就是在直線上是沒有問題的）。

當然，為了讓遊客在上面自由玩耍，IOIC 公園也希望道路的寬度越寬越好，也就是說，兩條平行直線的距離必須盡量大，同時，道路的兩側（三個區塊中的外側兩個）內也必須都要有至少一棵樹在裡面才行。

IOIC 公園想知道在給定的這 $N$ 棵樹下，最寬的道路可以多寬？請寫一支程式幫助他們找出這個寬度。

Input Format

輸入首行有一個正整數 $N$，代表樹的數量。

接下來 $N$ 行，每行兩個整數 $x_i, y_i$，代表第 $i$ 棵樹的座標。

  • $2 \leq N \leq 1200$
  • $0 \leq x_i, y_i \leq 10^ 9$
  • 不存在三棵樹的座標共線。

Output Format

輸出道路最寬可以是多寬。

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

Sample Input 1

3
1 1
2 1
3 2

Sample Output 1

1.414213562373

Hints

Problem Source

IOICamp 2022 Day5 pH

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~16 $N \leq 200$ 30
3 0~33 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 3
1 4000 524288 65536 2 3
2 4000 524288 65536 2 3
3 4000 524288 65536 2 3
4 4000 524288 65536 2 3
5 4000 524288 65536 2 3
6 4000 524288 65536 2 3
7 4000 524288 65536 2 3
8 4000 524288 65536 2 3
9 4000 524288 65536 2 3
10 4000 524288 65536 2 3
11 4000 524288 65536 2 3
12 4000 524288 65536 2 3
13 4000 524288 65536 2 3
14 4000 524288 65536 2 3
15 4000 524288 65536 2 3
16 4000 524288 65536 2 3
17 4000 524288 65536 3
18 4000 524288 65536 3
19 4000 524288 65536 3
20 4000 524288 65536 3
21 4000 524288 65536 3
22 4000 524288 65536 3
23 4000 524288 65536 3
24 4000 524288 65536 3
25 4000 524288 65536 3
26 4000 524288 65536 3
27 4000 524288 65536 3
28 4000 524288 65536 3
29 4000 524288 65536 3
30 4000 524288 65536 3
31 4000 524288 65536 3
32 4000 524288 65536 3
33 4000 524288 65536 3
Submit
Back to Top