闵可夫斯基和
闵可夫斯基和
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329408
几何上可以理解为B沿着A一周覆盖的图形。也可以是B偏移和A交的向量。
对两个凸包归并
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-10-04
分治 + 计算几何 + 闵可夫斯基和：ABC478G
分治 + 计算几何 + 闵可夫斯基和：ABC478G G - Division Point Hull 考虑用坐标点来表示 Qi,jQ_{i,j}Qi,j: Qi,j=qp+qPi+pp+qPjQ_{i,j}=\frac q{p+q}P_i+\frac p {p + q}P_j Qi,j=p+qqPi+p+qpPj 我们考虑分治来处理。先递归得到左右两边 QQQ 组成的凸包 QL,QRQ_L,Q_RQL,QR 我们现在需要得到跨区间 QQQ。根据上面的式子，我们发现其实我们只需要得到左右两边 PPP 组成的凸包，然后左边缩小到 qp+q\dfrac q{p+q}p+qq...
2021-12-11
【P5931 [清华集训2015]灯泡】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15675706.html 题目链接 题目 相比 WildleopardWildleopardWildleopard 的家，他的弟弟 MildleopardMildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。 ...
2021-12-11
【Loj #10013. 「一本通 1.2 例 3」曲线】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674711.html 题目链接 题目 明明做作业的时候遇到了 nnn 个二次函数 Si(x)=ax2+bx+cS_i(x)= ax^2 + bx + cSi(x)=ax2+bx+c，他突发奇想设计了一个新的函数 F(x)=max{Si(x)},i=1…nF(x) = max{S_i(x)}, i = 1ldots nF(x)=max{Si(x)},i=1…n。 明明现在想求这个函数在 [0,1000][0,1000][0,1...
2021-11-14
坐标系中三角形面积求法
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551910.html 之前打atcoder时不会这个东西，下大分，现在赶快补 仅用于个人备忘 坐标系中三角形面积求法 已知三角形三点坐标为 A(x1,y1),B(x2,y2),C(x3,y3)A(x_1, y_1),B(x_2, y_2), C(x_3, y_3)A(x1,y1),B(x2,y2),C(x3,y3) 则三角形面积为： S△ABC=∣(x2−x1)(y3−y1)−(x3−x1)(y2−y1)∣2S_{\triangl...
2023-12-22
计算几何+欧拉回路合并：1222T2
计算几何+欧拉回路合并：1222T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135152697 http://47.92.197.167:5283/contest/435/problem/2 2度点直接求夹角即可，4度角我是贪心选最小的情况。 但比如这样子： 我们会贪心选了4个蓝色角，形成红色和黄色两个欧拉回路，这就不是一个欧拉回路了。因此我们要考虑欧拉回路合并。 发现我们对于每个点划分成的两个集合各选一条边练一起，就可以合并两个欧=拉回路了。我们...
2023-12-21
平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048
平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135133585 https://qoj.ac/problem/5048 因此我们可以平面图转对偶图，如下图，假如我们割黄边，就是给所有蓝边加黄边的权值 每次找一条边权最小的边，满足它恰好有一侧是无界区域。将它删 去，将它的边权加到它所在最小环的其他边上。可以证明这个操作前后 任意两点的最大流大小不变。 对于转最小环的过程，我...