20006. 2-Dimensional Closest Pair Problem (Design Strategies for Computer Algorithms)

I'm a slow walker, but I never walk backwards.

輸入格式

每組測資第一行包含一個正整數 ($ \leq 25 \times 10^4$),代表點的個數,下一行開始每包含兩個正整數 $𝑥$,$𝑦$ ($ \leq 20000$),代表該點的座標。

  • 保證不會有兩點在相同位置 ($x_{1} \neq x_{2}$ and $y_{1} \neq y_{2}$)

輸出格式

對於每組測資,第一行請輸出最近點配對的距離 (四捨五入至小數點兩位) 和個數,下一行開始請輸出所有的配對。每組配對有兩個正整數,分別代表兩點輸入時的順序,且第一點為序號較小者。輸出時請依第一點序號遞增排序,若第一點序號相等,則依第二點序號遞增排。

  • 最近點配對總數不超過 $5 \times 10^5$

範例輸入 1

9
4630 3958
637 9585
4911 15241
8693 4792
11661 10667
10069 15094
15346 1347
14765 8063
13718 13376

範例輸出 1

3401.46 1
5 9

範例輸入 2

9
1108 3991
1679 8588
3981 18409
12268 6050
9210 9969
8601 18191
18783 380
17297 9099
17173 13924

範例輸出 2

4625.14 1
3 6

Discussion