最远点对

题目描述

求$n$个点中相距最远的两个点的距离

输入

第一个数为点的个数$n$

接下来$n$行，每行2个浮点数$x$，$y$，表示点的坐标

输出

一个浮点数，表示最远的距离，保留6位小数。

样例1

输入:
2
0 0
1 1
输出:
1.414214

样例2

输入:
4
0 1
1 0
1 1
-1 -1
输出:
2.828427

数据范围

$2 \leq n \leq 100000$

hint

直接用$O(n^2)$的算法可以拿$21.4286\%$的分数，先求出凸包再对凸包上的点使用$O(n^2)$的算法可以拿到$64.2857\%$的分数，求出凸包再对凸包上的点使用$O(n)$的算法可以拿到$100\%$的分数