多圆求面积并

《多圆求面积并》由会员分享，可在线阅读，更多相关《多圆求面积并（14页珍藏版）》请在金锄头文库上搜索。

1、 算法参照 AekdyCoin 的 Blog 开始看的时候觉的很多地方没讲清楚，所以决定rewrite 一遍。 感谢黄伟老湿的大力支持。 多圆面积并这个东西自己也只是听说过几次，觉得挺神奇的， 不会写， 前几天遇到一题孜孜 YY 了一个用多圆面积并+多圆与矩形面积并的算法，当时不会这个，比赛结束后就果断被拉去学了。 题目来源：http:/www.spoj.pl/problems/CIRU/ 题意： 给你 1000 个圆， 求这 1000 个圆的并集的面积。 举个栗子，下图是三个圆并的一种情况。 初看可能觉得毫无头绪，下面我们把轮廓标记一下。 仔细分析不难发现边界的轮廓都是只被覆盖一次的圆周。

2、那么我们就利用这个轮廓来把这三个圆的并给划分一下吧。 分法有很多，只要把轮廓分开了都是可以的，给一个比较直观的分法， 连接在轮廓线上的相邻两个圆交点，如下图所示。 这样分割之后，我们就把这三个圆的并集划分成了三个弓形+一个三角形。 这些形体的面积都是比较容易计算的。 那么处理多圆面积并就有了一个比较好的算法： 1、 去除被包含的圆，或者退化成点的圆。 2、 找到只被覆盖一次的圆弧， 然后把图形分成若干个弓形和若干个多边形 3、 计算面积。 怎么找只被覆盖一次的圆弧呢？ 首先，我们枚举一个圆，然后求出其他所有圆与它的交点（交点数少于两个可以直接忽略不计）。 先直接贴 AC 牛的一段话 引用 PS

3、.以下算法基于正方向为逆时针逆时针 考虑上图中的蓝色圆,绿色的圆和蓝色的圆交于 A,B 2 个交点 ,我们在逆时针系下考虑，那么 可以知道 对于蓝色的圆，它对应的某个 角度区间被覆盖了角度区间被覆盖了 假设 区间为 A, B, 并且角度是按照 圆心到交点的 向量的 极角来定义 (为了方便，我一般都把角度转化到 0,2pi区间内) 那么可以知道在这种 标识情况下，可能存在以下情况 这种区间的跨度如何解决呢?实际上十分简单， 只需要把A,B 拆成 A, 2PI, 0,B即可,也就是所谓的添加虚拟点 这上面这一段话定义了被覆盖了的角度区间被覆盖了的角度区间 我们求出所有与它相交的圆对应的被覆盖了的角

4、度区间，那么查找只被覆盖一次的圆弧就可以转换成查找只被覆盖了一次的区间了，这个实现起来是非常简单的。 找到了这些区间后，一个区间对应了一个弓形以及多边形上的一条边，面积是可以直接计算的。 首先是弓形。 对于 a1 角对应的弓形面积，可以看成一个 a1 角对应的扇形面积减去一个三角形的面积，不难得出 弓形面积解决了接下来是多边形的面积。 给个大一点的栗子，今天凌晨画的。 有多个多边形？这怎么搞？ 当然，还有更猎奇的。 这个多边形虽然鬼畜，但它肯定是简单多边形，既然是简单多边形，我们就可以利用叉积直接搞出来。 叉积有个很好的性质，就是它的值等于两个向量组成的一个平行四边形的有向面积，而这个面积根据

5、向量ab 的夹角还是有正负之分的，按照 ab 夹角为逆时针方向取正。 对于这个五边形 QRSTU，我们按照逆时针顺序将五条边定向，假设原点为(0,0)，那么，按照这五条边的方向将这些相邻的两个点一次叉乘然后除以二然后累加会得到什么东西呢？ 上面说了，叉乘的值等价于两个向量组成的一个平行四边形的有向面积，除以二就是以这两个向量为边的三角形有向面积了。所以，这个和为 S(OUT)+S(OTS)+S(OSR)+S(ORQ)-S(OQU) = S(QUTSR) 恰好是这个五边形的面积。而且，计算的时候不需要考虑不同边之间的先后顺序。 这个方法可以计算任意简单多边形的面积，只需要把每条边与原点构成的三角形的有向面积求出来然后累加即可。 总体复杂度是 O(n2 logn)的。 扩展： https:/www.spoj.pl/problems/CIRUT/url 给你 N 个不同的圆，求被覆盖了 K 次的面积，K 从 1取到 N。 这个的处理方法和被覆盖一次的面积处理方法一样，自己画个图，把被覆盖一次的圆弧连接起来，把覆盖两次的圆弧连接起来，把覆盖三次的圆弧连接起来答案就出来了。 下图是三个圆相交的情况。 黑色为被覆盖一次的圆弧 蓝色为被覆盖两次的圆弧 紫色为被覆盖三次的圆弧 至于怎么做什么的，人家才不告诉你呢