LuoguLOJ分析设第一个部落的领地为 $A$，第二个部落的领地为 $B$。假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点再利用叉积...
Luogu分析发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。于是把每张信用卡的四个顶点拿出来，求一个凸包，再用这个凸包的周长加上 $2\pi r$ 就是答案了。具体怎么求出四个顶点，可以先求出中心点，然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。然后就做完了。代码//It is made by M_sea #include <algorithm> #i...
Luogu分析将删除变成添加，然后用set来维护上凸壳即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cma...
BZOJ分析注意到 $111>3\times 20$ ，也就是说尽量多的围住 $\mathrm{tree}$ 是最好的。于是先求一个固定点的凸包，然后先不管在凸包外面的 $\mathrm{tree}$ 。现在的问题等价于，用最少数目的固定点，围住所有 $\mathrm{tree}$。于是就和合金那题一模一样了，建出图找最小环即可。特判一下所有 $\mathrm{tree}$ 都在凸包外...
LuoguBZOJ分析显然选的点要在凸包上。于是先求出凸包。然后，旋转卡壳确定一条对角线，然后$O(n)$扫描，找到对角线左右两个面积最大的三角形，合起来就是四边形的面积。总时间复杂度$O(n^2)$。代码#include <algorithm> #include <iostream> #include <cstdlib> #include <cst...
LuoguPOJ分析旋转卡壳板子题。求出凸包后直接上旋转卡壳就行了。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <...