[POJ2187][BZOJ1069]旋转卡壳

旋转卡壳

　　到现在依然不确定要怎么读...

　　以最远点对问题为例，枚举凸包上的两个点是最简单的想法，时间复杂度O（n²）

　　我们想象用两条平行线卡着这个凸包，当其中一个向某个方向旋转的时候另一个显然也是朝同样的方向旋转

　　所以在枚举其中一条边的过程中完全没有必要重新枚举另一条边

　　而且对于一条边而言，凸包上的点到这条边的距离是满足单峰性质的

　　所以线性的做法就出来啦

　　↓代码非常短很优秀~

　　[UPD.05.11]:回过头来复习的时候猛然发现这里没有讲它过程的原理...

　　为什么叉积大的离水平线的距离更远一些？因为叉积可以表示(i,i+1,j)三点构成三角形的面积的两倍

　　而三角形面积=1/2底*高在这里也就是线段(i,i+1)*点j到水平线的距离，所以叉积越大距离就越远了~

　　然而由于使用旋转卡壳是在已经求出凸包的基础之上的，所以叉积的值必为正，就不用考虑负面积的问题了

procedure Roatating_Calipers;

begin

　　stack[len+]:=stack[];j:=;

　　ans:=;

　　for i:= to len do

　　begin

　　　　while cross(stack[i],stack[i+],stack[j])<cross(stack[i],stack[i+],stack[j+]) do j:=j mod len+;

　　　　ans:=max(ans,max(getdis(stack[i],stack[j]),getdis(stack[i+],stack[j+])));

　　end;

end;

　　POJ2187 最远点对问题直接用RC

　　BZOJ1069 可以枚举一条对角线，在两边各找出一个点使得面积和最大，两边在保证在某个区间内的情况下做RC

　　BZOJ1185 是一道非常好的题，但目前还没有A掉...昨天奋战了一个晚上但在精度问题上还是卡住了

　　最小矩形根据黑书上的写法采用最小角前进，然而黄学长的做法代码又短又好看

　　发现只要引入点积会有一些奇妙的性质

　　在确定了一条边的时候找最远的边直接是裸的RC

　　然而怎么找这个矩形里最左的点和最右的点？

　　结论：点积越大越右，点积越小越左。

　　这个稍加证明即可。

巴特西

[POJ2187][BZOJ1069]旋转卡壳

最新文章

热门文章