标签 计算几何 下的文章
- 首页
- 计算几何
洛谷3297 [SDOI2013]逃考
Luogu分析首先求出每个亲戚管辖的区域，这个可以通过半平面交求出。具体的，将该亲戚与其它所有亲戚的中垂线拿出来跑半平面交即可。然后考虑建这样一个图：对于每个亲戚，往与它的管辖区域相邻的亲戚连边。这样子只要 BFS 求出走到外面的最短路就是答案了。注意要判掉 $n=0$ 的沙雕情况，不然你可能...
洛谷4250 [SCOI2015]小凸想跑步
LuoguLOJ分析假设有两个三角形 $\triangle ABO$ 和 $\triangle CDO$ ，且 $S_{\triangle ABO}<S_{\triangle CDO}$ 。设 $A(x_a,y_a),B(x_b,y_b),C(x_c,y_c),D(x_d,y_d),O(...
洛谷5286 [HNOI2019]鱼
LuoguLOJ分析口胡一时爽，写题火葬场显然可以枚举 $A$ 和 $D$ ，再算 $EF$ 和 $BC$ 的方案数。$EF$ 比较好算：按极角序枚举 $A$ ，那么直接双指针扫所有的点并类似莫队更新答案即可。$BC$ 就比较难算。注意到 $AD$ 对 $BC$ 的限制很强，那么我们可以先枚举...
洛谷5328 [ZJOI2019]浙江省选
LuoguLOJ分析我们把每个人看做一条直线。首先做一遍半平面交（简单版）那么在半平面交上的人都可以拿第一名。接着考虑第二名。显然如果一个人想要拿第二名，那么他至少在剩下的人中要能拿到第一名。那么先跑一遍半平面交，然后得到所有第二名的候选人。再把所有第一名拿出来，对每个人二分求出一个范围 $[...
洛谷5302 [GXOI/GZOI2019]特技飞行
LuoguBZOJLOJ分析感谢 $\mathrm{\color{black}{y}\color{red}{ch}}$ 的讲解qwq首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ ...
洛谷3829 [SHOI2012]信用卡凸包
Luogu分析发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。于是把每张信用卡的四个顶点拿出来，求一个凸包，再用这个凸包的周长加上 $2\pi r$ 就是答案了。具体怎么求出四个顶点，可以先求出中心点，然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。然后就做完了。另外，...
洛谷3454 [POI2007]OSI-Axes of Symmetry
LuoguBZOJ分析把每条边的长度和每个角的大小按顺序排列，可以组成一个环。把这个环在某条对称轴的地方断开，形成的串显然是回文的。于是把这个环倍长，然后长度 $> len$ 的回文串个数就是答案（这里的 $len$ 是环长）。直接跑 $\mathrm{manacher}$ 即可。具体的...
洛谷2533 [AHOI2012]信号塔
LuoguBZOJ双倍经验分析最小圆覆盖的板子题。首先将输入的点随机打乱，然后三重循环枚举三个点 $i$ 、 $j$ 、 $k$ 。如果 $i$ 不在当前圆内，将圆心设为 $i$ 。如果 $j$ 也不在圆内，将圆心设为 $i$ 和 $j$ 的中点。如果 $k$ 也不在圆内，将圆心设为 $△ij...
洛谷2521 [HAOI2011]防线修建
Luogu分析将删除变成添加，然后用set来维护上凸壳即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cs...
BZOJ1390 [CEOI2008]Fence
BZOJ分析注意到 $111>3\times 20$ ，也就是说尽量多的围住 $\mathrm{tree}$ 是最好的。于是先求一个固定点的凸包，然后先不管在凸包外面的 $\mathrm{tree}$ 。现在的问题等价于，用最少数目的固定点，围住所有 $\mathrm{tree}$。于是...