P2698 [USACO12MAR] Flowerpot S
题目描述
老板需要你帮忙浇花。给出 $N$ 滴水的坐标，$(x,y)$ 表示水滴最初的坐标。
每滴水均以每秒 $1$ 个单位长度的速度下落。你需要把花盆放在 $x$ 轴上的某个位置，使得花盆接到第 $1$ 滴水与最后 $1$ 滴水之间的时间差至少为 $D$。
如果水滴落在 $x$ 轴上的位置与花盆的边沿对齐，也认为被接住。
给出 $N$ 滴水的坐标和时间差 $D$ ，请算出最小的花盆宽度 $W$。
输入格式
无
输出格式
无
说明/提示
**【样例解释】**
有 $4$ 滴水，初始位置分别在 $(6,3)$，$(2,4)$，$(4,10)$，$(12,15)$。水滴至少用 $5$ 秒时间先后落入花盆。花盆的宽度为 $2$ 是必须且足够的，此时把花盆放在 $x=4\dots6$ 的位置，它可以接到水滴 $1$ 和 $3$ ，之间的时间差为 $10-3=7$，满足条件。
**【数据范围】**
$40\%$ 的数据：$1 \le N \le 1000$ ，$1 \le D \le 2000$。
$100\%$ 的数据：$1 \le N \le 10 ^ 5$，$1 \le D \le 10 ^ 6$，$0\le x,y\le10^6$。