洛谷5617 [MtOI2019]不可视境界线
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
标签 计算几何 下的文章
- 首页
- 计算几何
CF528E Triangles 3000
Codeforces Luogu 分析 考虑三角形的面积公式：$S_{\triangle ABC}=\frac{1}{2}\left(\vec{OA}\times\vec{OB}+\vec{OB}\times\vec{OC}+\vec{OC}\times\vec{OA}\right)$，其中 $ABC$ 是逆时针顺序。 于是可以枚举一条直线 $l_i$，然后枚举另一条直线 $l_j$，计算它...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3517 [POI2011]WYK-Plot
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...
CF1284E New Year and Castle Construction
Codeforces Luogu 分析 考虑任意五个点对答案的贡献。显然有 如果五个点的凸包为五边形，则贡献为 $0$； 如果五个点的凸包为四边形，则贡献为 $1$； 如果五个点的凸包为三角形，则贡献为 $2$。 我们只需要求出五个点凸包为为 $x$ 边形的方案数 $s_x$，然后答案即为 $s_4+2s_3$。 不知道怎么想到可以把答案拆成 $5(s_5+s_4+s_3)-(5s_5+...
洛谷4518 [JSOI2018]绝地反击
Luogu LOJ 分析 设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。 考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。 这样子可能过不了，考虑一些优化。我们预...
洛谷4557 [JSOI2018]战争
Luogu LOJ 分析 设第一个部落的领地为 $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$ 内，二分出极角相邻的点...
CF1254C Point Ordering
Codeforces Luogu 分析 首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。 接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。 我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们...
洛谷3297 [SDOI2013]逃考
Luogu 分析 其实就是要求 Voronoi 图的对偶图最短路。 可以通过半平面交求出 Voronoi 图的每个区域，然后对于每条直线连边即可。 然后直接跑 BFS 就好了。 注意特判 $n = 0$。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.c...
BZOJ2395 [Balkan 2011]Timeismoney
BZOJ 分析 我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。 这个东西可以分三步求： 求出与 $x$ 轴和 $y$ 轴最近的点 这个还是很简单的。 把 $a_i$ 作为边权，求出的最小生成树...