P16042 [ICPC 2022 NAC] Cookie Cutter

人人都爱巧克力曲奇！但不幸的是，这意味着有时候需要分享。在这里，你慷慨地同意与你的朋友分享一块正方形的巧克力曲奇。 因为这是你的曲奇，所以你可以选择如何切割，以及将哪一块分给朋友。你可以沿着任意一条穿过曲奇的直线进行切割，直线不必与坐标轴平行。 你知道曲奇中所有巧克力碎粒的位置。由于你更喜欢巧克力碎粒密集的曲奇，因此你想优化切割方式，以得到最好的分配结果。具体来说，你要最大化你的那块曲奇中巧克力碎粒所占比例与曲奇面积所占比例之差。

输入的第一行包含两个空格分隔的整数 $n$（$2 \le n \le 10{,}000$）和 $m$（$1 \le m \le 3{,}000$），其中 $n$ 是正方形曲奇的边长，$m$ 是曲奇中巧克力碎粒的数量。 接下来的 $m$ 行，每行包含两个空格分隔的整数 $x$ 和 $y$（$0 < x, y < n$），表示一个巧克力碎粒在曲奇中的位置。所有巧克力碎粒的位置互不相同。如果某个巧克力碎粒恰好位于切割线上，你可以决定将它归入哪一块曲奇。

输出一个实数，表示 $\frac{b}{m} - \frac{a}{n^2}$ 的最大可能值，其中 $a$ 是你分得的曲奇面积，$b$ 是你分得的曲奇中的巧克力碎粒数量。答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

:::align{center}  样例 1 示意图。 ::: 翻译由 DeepSeek V3.2 完成