#P9352. [SDOI2012] 最近最远点对

    ID: 5752 传统题 1000ms 256MiB 尝试: 11 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-最近点对分治检查条带双指针合并有序序列Andrew 算法旋转卡壳叉积平方距离比较

[SDOI2012] 最近最远点对

题目描述

给定平面上的 nn 个点。考虑所有由两个不同下标组成的点对,分别求欧氏距离的最小值和最大值。若两个点的坐标重合,其距离为 00。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个非负实数 xi,yix_i,y_i,表示第 ii 个点的坐标。

输出格式

输出一行两个实数,依次为最短距离和最长距离。每个值的绝对误差或相对误差不超过 10−410^{-4} 即可。

4
0.0 0.0
0.0 1.0
1.0 0.0
1.0 1.0
1.0000 1.4142

数据范围

本站评测保证 2≤n≤1052\le n\le10^5,0≤xi,yi≤1090\le x_i,y_i\le10^9。

  • 对于 30%30\% 的数据,n≤2000n\le2000。
  • 对于 70%70\% 的数据,n≤20000n\le20000。