poj 3301 Texas Trip (三分,模板题)

题目链接

题意:

给定二维平面的n个点,要求一个面积最小的正方形,使其能覆盖所有的点。

思路:

先考虑如果水平竖直地放置正方形(边和坐标轴平行)圈住所有点的最小正方形的边长是:

L=max(xmaxxmin,ymaxymin)
然后考虑如果正方形旋转的话,能圈住所有点的正方形边长是随着角度先减后增的,有凸性,可以三分。。。
但是枚举角度计算正方形的话比较麻烦,可以选择旋转平面上的点,使得正方形仍然是水平竖直放置的,因为这样计算正方形的边长比较方便。
如果把点表示成极坐标形式:

x=r×cosθ,y=r×sinθ,θ

那么顺时针旋转 α 角度后:

x=r×cos(θα),y=r×sin(θα)

化简一下可得:

x=r×cosθ×cosα+r×sinθ×sinα=x×cosα+y×sinα
y=r×sinθ×cosαr×cosθ×sinα=y×cosαx×sinα
然后就是三分角度了。。。
三分的板子:

 


 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz