CodeforcesLuogu分析考虑一个贪心,即每次取贡献最大的一个,这里的贡献是 $k_i\times a_i+b_i$,其中 $k_i$ 表示前面选了的数量,$b_i$ 表示后面选了的 $a_i$ 的和。那么我们相当于要维护一些直线,支持区间斜率加、截距加和求全局最大值。考虑分块,对每块维护一个上凸壳,散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。代码// =======...
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 <...