「SHOI2011」直线拟合

题目传送门。

题目大意是求一条直线使得所有点到直线距离的最大值最小。

一个可以想到的方法是二分，但是直线无法表示，不能直接 check。

因为要考虑点距离的最大值，容易想到凸包，又要求距离最小，那么这个距离应该是凸包宽度的一半。

用旋转卡壳的方法求出这个宽度，输出它的一半即可。

可以发现，这里最小宽度应该是一个点线距，卡的是一条边和它对应的点。

时间复杂度为：，空间复杂度为：。

代码在这里。