标签 计算几何 下的文章
- 首页
- 计算几何
洛谷5377 [THUPC2019]鸽鸽的分割
LuoguLOJ分析将整个蛋糕看做平面图，由欧拉公式可得代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ===================...
UVA12123 Magnetic Train Tracks
UVaLuoguVjudge分析感觉...挺傻逼的？锐角三角形和直角三角形似乎不是很好数的亚子，可以考虑拿总数 $n\choose 3$ 减掉钝角三角形的数量。枚举一个点 $A$ ，按极角序枚举另一个点 $B$ ，那么极角在 $(ang_B+\frac{\pi}{2},ang_B+\pi)$ ...
UVA11529 Strange Tax Calculation
UVaLuogu分析一道不错的数数题。首先可以知道，三角形总数是 $n\choose 3$ ，所以只需要求出所有三角形包含的点数之和即可。可以转化一下，变成求每个点被多少个三角形包含。这个东西等于 $n-1\choose 3$ 减去不包含这个点的三角形个数。于是我们重点考虑怎么求不包含一个点 ...
洛谷4423 [BJWC2011]最小三角形
LuoguBZOJ文化课选手M_sea更博了！分析分治。按照“平面最近点对”那一套理论，选取一条中心线划成两半，这样子最小三角形会有三种情况：全部在中心线左边。全部在中心线右边。一部分在左边，一部分在右边。显然第一种和第二种递归下去即可，主要考虑第三种怎么处理。设当前的最小周长为 $ans$ ...
洛谷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}$。于是...
洛谷3249 [HNOI2016]矿区
LuoguBZOJ分析首先将平面图转成对偶图。考虑怎么找到一个平面区域。首先把双向边转成两条单向边，这样每条边都属于一个区域。然后将以每个点为起点的边按极角排序。对于每条边$(u,v)$，在以$t$为起点的边中找到$(v,u)$，排序后它的上一条边就是当前区域的下一条边。这样一直到区域闭合，就...