CF1254C Point Ordering
CodeforcesLuogu分析首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们到 $A_...
标签 计算几何 下的文章
- 首页
- 计算几何
洛谷3222 [HNOI2012]射箭
Luogu分析除了卡精度都很简单的题。显然二分答案，考虑如何 check。设抛物线为 $y=ax^2+bx$，那么对于每个 $i$ 都应有那么对于每个 $i$，$a,b$ 的解集都可以表示为两个半平面的交，因此我们只要把 $2\times mid$ 个半平面拿出来判断是否存在半平面交即可。这题卡精度卡的我想死了 QAQ代码// ================================...
洛谷5377 [THUPC2019]鸽鸽的分割
LuoguLOJ分析将整个蛋糕看做平面图，由欧拉公式可得代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #inclu...
UVA12123 Magnetic Train Tracks
UVaLuoguVjudge分析感觉...挺傻逼的？锐角三角形和直角三角形似乎不是很好数的亚子，可以考虑拿总数 $n\choose 3$ 减掉钝角三角形的数量。枚举一个点 $A$ ，按极角序枚举另一个点 $B$ ，那么极角在 $(ang_B+\frac{\pi}{2},ang_B+\pi)$ 范围内的点 $C$ 都可以和 $A,B$ 组成一个钝角三角形。那么直接拿两个指针扫一下就好了。可以发...
UVA11529 Strange Tax Calculation
UVaLuogu分析一道不错的数数题。首先可以知道，三角形总数是 $n\choose 3$ ，所以只需要求出所有三角形包含的点数之和即可。可以转化一下，变成求每个点被多少个三角形包含。这个东西等于 $n-1\choose 3$ 减去不包含这个点的三角形个数。于是我们重点考虑怎么求不包含一个点 $x$ 的三角形个数。把除了 $x$ 之外的所有点拿出来，按极角序排序后扫描。假设当前扫到了 $i$...
洛谷4423 [BJWC2011]最小三角形
LuoguBZOJ文化课选手M_sea更博了！分析分治。按照“平面最近点对”那一套理论，选取一条中心线划成两半，这样子最小三角形会有三种情况：全部在中心线左边。全部在中心线右边。一部分在左边，一部分在右边。显然第一种和第二种递归下去即可，主要考虑第三种怎么处理。设当前的最小周长为 $ans$ ，那么先把所有离中心线的 $x$ 的差不超过 $ans$ 的点拿出来按 $y$ 排个序。枚举一个点 ...
洛谷3829 [SHOI2012]信用卡凸包
Luogu分析发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。于是把每张信用卡的四个顶点拿出来，求一个凸包，再用这个凸包的周长加上 $2\pi r$ 就是答案了。具体怎么求出四个顶点，可以先求出中心点，然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。然后就做完了。代码//It is made by M_sea #include <algorithm> #i...
洛谷3454 [POI2007]OSI-Axes of Symmetry
LuoguBZOJ分析把每条边的长度和每个角的大小按顺序排列，可以组成一个环。把这个环在某条对称轴的地方断开，形成的串显然是回文的。于是把这个环倍长，然后长度 $> len$ 的回文串个数就是答案（这里的 $len$ 是环长）。直接跑 $\mathrm{manacher}$ 即可。具体的，长度可以不开根号，角的大小可以用叉积。然后最后的答案要 $/2$ ，因为每条对称轴被算了两次。具...
洛谷2533 [AHOI2012]信号塔
LuoguBZOJ双倍经验分析最小圆覆盖的板子题。首先将输入的点随机打乱，然后三重循环枚举三个点 $i$ 、 $j$ 、 $k$ 。如果 $i$ 不在当前圆内，将圆心设为 $i$ 。如果 $j$ 也不在圆内，将圆心设为 $i$ 和 $j$ 的中点。如果 $k$ 也不在圆内，将圆心设为 $△ijk$ 的外心。可以证明期望复杂度为 $O(n)$ 。代码//It is made by M_sea ...
洛谷2521 [HAOI2011]防线修建
Luogu分析将删除变成添加，然后用set来维护上凸壳即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cma...