向量
基本运算
点积:$a\cdot b=|a||b|\cos\langle a,b\rangle$,写成坐标形式是 $a\cdot b=x_ax_b+y_ay_b$。
叉积:$a\times b=|a||b|\sin\langle a,b\rangle$,写成坐标形式是 $a\times b=x_ay_b-y_ax_b$。
极角排序
只按照叉积的正负来排的话会导致 $a<a$ 出现。正确的方法是先按照象限排,再按照叉积排。
向量旋转
用和差角公式或者复数推都可以。
左旋 $\theta$ 得到的是 $(x\cos \theta-y\sin \theta,x\sin \theta+y\cos \theta)$。
线段
存线段的方法是存线段上的两点。
多边形
多边形面积
$$ \frac{1}{2}\sum_{i=0}^{n-1} |P_i\times P_{(i+1)\bmod n}|. $$
求凸包
把点集按照 $(x,y)$ 双关键字排序。然后正着扫一遍求下凸壳,再倒着扫一遍求上凸壳。
求凸包直径
旋转卡壳。逆时针扫凸包上的边,维护其对应的最远点。求答案时把这条边的两个端点到最远点的距离取 $\max$。
题目
给定 $n$ 个点,保证它们形成一个凸多边形,对于其中每个点求它到其他点的最大距离。
没法旋转卡壳,但这东西是有决策单调性的,直接分治就行了。