闵可夫斯基和
闵可夫斯基和
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329408
几何上可以理解为B沿着A一周覆盖的图形。也可以是B偏移和A交的向量。
对两个凸包归并
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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-12-15
【P2571 [SCOI2010]传送带】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15693858.html 题目链接 题目 在一个 222 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 AB\text{AB}AB 和线段 CD\text{CD}CD。lxhgww 在 AB\text{AB}AB 上的移动速度为 PPP，在 CD\text{CD}CD 上的移动速度为 QQQ，在平面上的移动速度 RRR。现在 lxhgww 想从 A\text AA 点走到 D\text DD 点，他想知道最少需要走多...
2021-11-18
【P2352 队爷的新书】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574898.html 题目链接 可以发现，我们并不需要对所有节点进行枚举，我们只需要对所有端点甚至只需要枚举右端点即可。 因为如果这个不是端点，那么在它右边的点和它所在的区间个数相同，同时右边的点必然大于这个点，所以不用考虑这个点。 按照线段覆盖问题求出每个点的覆盖情况即可，也可以说是一维扫描线（雾 时间复杂度：O(nlogn)O(n\log n)O(nlogn)，主要是排序耗时间。 Code 12345678910111213141516...
2021-12-11
【P5931 [清华集训2015]灯泡】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15675706.html 题目链接 题目 相比 WildleopardWildleopardWildleopard 的家，他的弟弟 MildleopardMildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。 ...
2023-10-20
计算几何+2sat：1020T3
计算几何+2sat：1020T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133943270 http://cplusoj.com/d/senior/p/SS231019C 我们进行这样的转化 则0/1必选一个，2/3必选一个 那么就变成一个2sat问题 两三角形有交，则一个选，一个不能选 对角三角形一个选，一个不选。一个不选，一个选 三角形不合法，则选向不选连边，代表必须不选 123456789101112131415161718192021222...
2026-07-02
计算几何 Geometry 知识Preview
计算几何 Geometry 知识Preview 本文章不追求彻底搞懂计算几何，只追求先把计算几何最基础的知识点和工具大致过一遍，建好知识体系与知识框架 向量 Vector 外积 Product 仅在三维向量空间中适用，记为 a×ba\times ba×b，其定义如下： ∣a×b∣=∣a∣∣b∣sin<a,b>|a\times b|=|a||b|\sin\left<a,b\right>∣a×b∣=∣a∣∣b∣sin⟨a,b⟩ a×ba\times ba×b 与 a,ba,ba,b 均垂直，满足右手法则 接下来我们对于二维向量讨论： 坐标运算 a×b=x1y...