标签 凸包 下的文章

  1. 首页
  2. 凸包

CF573E Bear and Bowling

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

  • M_sea
  • 2020 年 08 月 08 日
  • 暂无评论

    • 洛谷4557 [JSOI2018]战争

    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$ 内，二分出极角相邻的点再利用叉积...

  • M_sea
  • 2020 年 02 月 19 日
  • 暂无评论

    • 洛谷3829 [SHOI2012]信用卡凸包

    Luogu分析发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。于是把每张信用卡的四个顶点拿出来，求一个凸包，再用这个凸包的周长加上 $2\pi r$ 就是答案了。具体怎么求出四个顶点，可以先求出中心点，然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。然后就做完了。代码//It is made by M_sea #include <algorithm> #i...

  • M_sea
  • 2019 年 04 月 02 日
  • 暂无评论

    • 洛谷2521 [HAOI2011]防线修建

    Luogu分析将删除变成添加，然后用set来维护上凸壳即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cma...

  • M_sea
  • 2019 年 03 月 07 日
  • 4 条评论

    • BZOJ1390 [CEOI2008]Fence

    BZOJ分析注意到 $111>3\times 20$ ，也就是说尽量多的围住 $\mathrm{tree}$ 是最好的。于是先求一个固定点的凸包，然后先不管在凸包外面的 $\mathrm{tree}$ 。现在的问题等价于，用最少数目的固定点，围住所有 $\mathrm{tree}$。于是就和合金那题一模一样了，建出图找最小环即可。特判一下所有 $\mathrm{tree}$ 都在凸包外...

  • M_sea
  • 2019 年 03 月 06 日
  • 暂无评论

    • 洛谷4166 [SCOI2007]最大土地面积

    LuoguBZOJ分析显然选的点要在凸包上。于是先求出凸包。然后，旋转卡壳确定一条对角线，然后$O(n)$扫描，找到对角线左右两个面积最大的三角形，合起来就是四边形的面积。总时间复杂度$O(n^2)$。代码#include <algorithm> #include <iostream> #include <cstdlib> #include <cst...

  • M_sea
  • 2019 年 01 月 27 日
  • 4 条评论

    • 洛谷1452 Beauty Contest

    LuoguPOJ分析旋转卡壳板子题。求出凸包后直接上旋转卡壳就行了。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <...

  • M_sea
  • 2019 年 01 月 23 日
  • 暂无评论