闵可夫斯基和
闵可夫斯基和
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329408
几何上可以理解为B沿着A一周覆盖的图形。也可以是B偏移和A交的向量。
对两个凸包归并
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-22
求两直线的旋转角
求两直线的旋转角 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135152729 如图，求 α\alphaα 。我们采用的是向量法+三角函数法 转化向量 ： (xb−xa,yb−ya),(xc−xb,yc−yb)(x_b-x_a,y_b-y_a),(x_c-x_b,y_c-y_b)(xb−xa,yb−ya),(xc−xb,yc−yb) 转化为向量后，相当于是求他们小于180度的夹角 可以先考虑求两个分别的角，再相减 已知...
2021-11-18
【P2352 队爷的新书】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574898.html 题目链接 可以发现，我们并不需要对所有节点进行枚举，我们只需要对所有端点甚至只需要枚举右端点即可。 因为如果这个不是端点，那么在它右边的点和它所在的区间个数相同，同时右边的点必然大于这个点，所以不用考虑这个点。 按照线段覆盖问题求出每个点的覆盖情况即可，也可以说是一维扫描线（雾 时间复杂度：O(nlogn)O(n\log n)O(nlogn)，主要是排序耗时间。 Code 12345678910111213141516...
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-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...
2021-12-11
【P5931 [清华集训2015]灯泡】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15675706.html 题目链接 题目 相比 WildleopardWildleopardWildleopard 的家，他的弟弟 MildleopardMildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。 ...
2023-12-21
平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048
平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135133585 https://qoj.ac/problem/5048 因此我们可以平面图转对偶图，如下图，假如我们割黄边，就是给所有蓝边加黄边的权值 每次找一条边权最小的边，满足它恰好有一侧是无界区域。将它删 去，将它的边权加到它所在最小环的其他边上。可以证明这个操作前后 任意两点的最大流大小不变。 对于转最小环的过程，我...