[POJ 3301]

Texas Trip

三分法。

其实一开始我是二分做的,二分的对象是正方形的边长,判断可行行则是将整幅图每次旋转一个微小角度,计算与坐标轴平行覆盖所有点的最小正方形。虽然这题精度和数据规模都一般,但还是妥妥的TLE了。于是看了讨论,又参考了这篇文章

思路还是很清晰的,旋转范围是[0,pi/2],在这范围内最短边长值是凹函数。于是对角度三分之后,计算所有点坐标中x、y两方向上的最大差值,并取较大值为此时正方形边长。迭代直到精度足够即可。

又学到了很实用的算法。 ^ ^