QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+3]

# 142. 平面最近点对

Statistics

题目描述

给定平面中的 n 个点 P(x,y),求:

min

输入格式

输入的第一行包含 1 个整数 n

接下来 n 行,每行 2 个整数 x,y

输出格式

输出一行一个实数。

样例数据

样例 1 输入

5
4 8
5 2
3 7
6 10
1 3

样例 1 输出

1.4142135623730950488016887242097

样例 2 输入

6
24 58
39 67
18 57
92 83
75 10
5 7

样例 2 输出

6.0827625302982196889996842452021

样例 3 输入

10
123 534
823 759
127 854
359 583
824 758
756 827
347 582
976 845
473 375
675 347

样例 3 输出

1.4142135623730950488016887242097

样例 4 输入

50
237 24
326 153
234 51
388 349
467 269
486 19
64 105
129 205
66 285
463 235
296 78
323 407
137 207
401 339
57 91
157 6
237 81
452 463
431 420
230 134
100 92
228 351
443 415
466 293
88 86
154 455
435 470
311 312
185 397
408 177
271 26
270 333
362 59
228 74
281 213
441 16
49 263
176 117
273 76
197 294
466 214
491 447
18 343
288 295
427 137
177 167
191 201
180 289
384 92
130 164

样例 4 输出

8.2462112512353210996428197119482

子任务

你的答案是正确的,当且仅当你的误差不超过 10^{-6}

对于所有数据,2 \leq n \leq 2 \times 10^61 \leq x_i, y_i \leq 10^{9}

Subtask 1(15分):n \leq 3000

Subtask 2(25分):n \leq 50000

Subtask 3(15分):n \leq 5 \times 10^5

Subtask 4(20分):n \leq 10^6

Subtask 5(25分):n \leq 2 \times 10^6