这是本文档旧的修订版!
题目大意:给定二维平面上的一个凸包,该凸包可绕对称轴任意旋转,求最终形成的立体的体积
若没有对称轴,则没有体积
若只有一条对称轴,则只需要找到这条对称轴,然后求若干圆台的体积和
若对称轴超过一条,则最终的立体是个球,其半径为凸包几何重心距凸包边界的最远点
求多边形对称轴
对于$n$个点的多边形,依次将夹角和边长存入数组,得到长为$2*n$的数组,然后将数组复制一遍接在后面,保证成环
用Manacher处理上述长为$4*n$的数组,不需要加入间隔符
对于位下标为$n+1$到$3*n$的位置,若其回文半径$\geq n$,则该位置存在一条对称轴,若位置对应为角,则经过该角顶点,若对应位置为边,则经过该边中点
为了避免精度误差,夹角可用点积,边长可用边长平方,这样可用保证数组内全为整数
按照题目给定的最小表示法对字符串进行后缀排序。
考虑在较短时间内对后缀 $S[i:]$ 和 $S[j:]$ 排序,要求在短时间内能求出两后缀的 $Lcp$ 即可。先预处理出每个后缀对应的字符大小关系,并求出每个字符出现位置的差分数组,并建立后缀自动机,在求 $Lcp$ 时需要按相对大小枚举每个字符,求出最早的失配位置,再取最小值就能得到 $Lcp$,注意特判第一个字符。
单次判断复杂度 $O(26)$,排序总复杂度 $O(26\times n\log n$)