圆的面积并
-
IOI2004
国家集训队第
3
轮作业
湖南省长沙市长郡中学
栗师
《圆的并》解题报告
1
、题目描述
①
给定
n(1
≤
n
≤
1000)
个圆，求
n
个圆的并的面积。圆的坐标和半径的范围是
-10000
到<
/p>
10000
，答案精确到小数点后面
6<
/p>
位。
2
、算法分析
关于求圆的并的方法有很多。
这中间有很多是求近似值的算法，
例如随机算
法，
割平面算法，
这些算
法都很简单，
当精度要求不高时，
使用这些算法是比较
好的选择。
但是，
如果精度要求高一点，
这些算法的复杂度也会大大的提高。
例
如这里
的数据范围，
用随机算法时最坏情况下至少需要随机
10
10
个点，
割平面算
法的复杂度也不止
1000*10
10
的级别。
这道题，我们只有用理论上能求出准确值的算法（不
考虑计算时的精度误
差）
。由于圆的并是一个很复杂的形状，直
接计算它的面积不是很容易，想法当
然是把它们分割成若干部分，
每一个部分求出它们的面积，
而每一部分的面积都
不是很难算
。
这样就不难想到离散交点的方法，
把所有的交点按照
x
坐标排序后，
对任意两个交点，用一条条的竖
直线去分割图形：
图
1
①
题目来源：经典问题
第
1
页
共
10
页
IOI2004
国家集训队第
3
轮作业
湖南省长沙市长郡中学
栗师
这样，
平面被分成若干条形区域，
怎样计算条形区域的面积呢？由于没有交
点，所以这个变得简单。
看图中绿色方框框住的区域里面
的圆，
就不难发现，
它可以分成若干梯形和
弓形的面积（下面的左图）
：
弓形
1
梯形
弓形
2
图
2
考虑一般的情况，
一个竖直区域的左右两条分界线，
一个圆与它们相交的情
况有
3
种：
不与任意一条分界线相交、
与其中一条相交，与两条都
相交
（相切不
算相交）
。其实如果把每
个圆的两条竖直切线都拿来离散，那么就只需要考虑圆
与两条竖直线都相交的情况了。<
/p>
两条分界线切割圆时，在两条分割线中会形成两条弧，上面和下
面各一条。
这些弧之间不可能有交点，
于是把它们的左的端点从
上到下排序，
左端点相同的
按照右端点排序。
< br>记一个层次，
然后再从上往下扫描，
遇到上边界就将层次
加
1
，
遇到下边界就将层次减
1
。到了层次为
0
的时
候，就形成了一个独立区域。这个
区域的面积可以通过两个弓形的面积和一个梯形的面积
相接计算出来。如图
2
的右，形成了两个独立区域，粉红色表示
层次为
1
，绿色表示层次为
2
，蓝色表
示层次为
3
。
第
2
页
共
10
页
IOI2004
国家集训队第
3
轮作业
湖南省长沙市长郡中学
栗师
再来分析算法的时间复杂度，最
坏情况下，交点个数的级别是
O(n
2
)
的，共
分成了
O(n
2
)
个区域，然后每一个区域都与
n
个圆相交，加上排序，复杂度是
O(n
< br>3
log
2
n)
的。
总感觉到题目描述很简单，
应该复杂度降低一些。
上面的算法很直观，
而下
面说的算法也比较直观，可以把复杂度降为
O(n
2
log
2
n)
。
试想，
如果人来做此题，
而不使用计算机计算，
那么，
人会采取什么样
的方
法呢？看下面的图：
两个圆相交
的情况，
可以把面积分成两个弓形
的面积
之和。
（上面
两个
图）
下面是三个圆两两相
交的情况，可以把面积看
成是
3
个弓形与一个三角
< br>形面积
之和。
（下面
两个
图）
图
3
图
4
第
3
页
共
10
页
IOI2004
国家集训队第
3
轮作业
湖南省长沙市长郡中学
栗师
看图
4
，
4
个圆，如上图所示，可以看成是<
/p>
8
个弓形（外面
4
个，里面
4
个）
的面积，再加上一个
4
边形面积（外面的
4
边形）
，再减去一个
4
边形面
积（里
面的
4
边形）
< br>。
上面的图形虽然简单，
人能
够很快的看出它是什么样的图形拼接而成，
但是，
如果圆的个数
多了一点，还能不能变得如此简单？
从图
3
的
3
个圆的情况可以看出，有些
交点是没有用到的！虽然
3
个圆有
6<
/p>
个交点，
但是，
只有
3
个交点在计算中起到了作用。
观察这
3
个点与另外
3
个点
的区别。
这
3
个圆的周围没
有完全被蓝色部分包围！
推广到一般的情况，
也可以
这样做。
首先要做一些预处理，
如果一个圆完全被另一个圆包围，
那么这一个圆可以
删
除。
删除后，
如果一个圆是孤立的圆，
不与其它任何圆相交，
就可以把这个圆
的面积现算出来，也将它
删去。剩下的工作就是求交点了。
对于一个圆来说，
其他的某些圆覆盖了他的圆弧上的某一段，
即若干个区间。
那么所有的圆覆盖的部分也是若干个区间。
如果有
k
个区间被覆盖了，
也就会有
k
个区间没有被覆盖。这
2k
个区间被
2k
个点分开。
已覆盖部
分
已覆盖部
分
未覆盖部
分
未覆盖部
分
图
5
图中黑色部分是被覆盖的部分，
即“看不见的”
，而绿色部分是为覆盖的部分，
即“露在外面的
”
，所以在计算弓形的面积时，绿色部分所围成的弓形一定会计
算在总面积中间。
所以我们用若干有向弦把这些部分分开，
有向
是指：
沿圆的逆
时针方向，如图
5
的右边所示。
对所有的圆都这样处理了以
后，
只看这些连线，
有什么发现？不难发现任意
第
4
页
共
10
页
IOI2004
国家集训队第
3
轮作业
湖南省长沙市长郡中学
栗师
一个分割点一定会有两条连线！
一条连线连进来，
一条连出去。
并且也
只会有两
条连线。
这个试着画就可以了，
例如如果
3
个圆经过通过同一个点，
那么其中一
定有一个圆，这个点的两边的弧都被覆盖了，即这个点不是这个圆的分割点！
如果任意一个分割点都会有两条连线，
那么，
这些连线之间形成了若干多边
形。
这些多边形就是我们要求的多边形的面积。
但是，
这些多边
形中有的面积是
负的，
这个只需要看这个多边形的连线是顺时针
的还是逆时针的，
顺的为正，
逆
的为负
。
用一个例子来说明这个算法。
图
6
然后再把一个被完全包含的圆和一个孤立的圆特殊处理删掉后，
就变
成了右
边的图。
注意还有一个圆它没有被任意一个圆完全包围，
但是它却没有圆弧露在
外面。
算法就是这样，
虽然没有严谨的证明来写，
但
是这样，
感性的认识多于理性
的思考，更容易使人理解。有些东
西，千言万语也表达不出来，而有些东西，无
法用言语表达，也不需要用言语表达。
该是分
析时
间复
杂度
的时候
了。
求每
一个
圆被覆
盖的
区间
的复
杂度是
O(nlog
n)
，
因为需要排序，
所以求所有的圆
的覆盖区间也只需要
O(n
2
logn
)
了。
而
算法其余的部分，
例如前面的预处理，
构造这些有向边，
以及计算多
边形的面积。
第
5
页
共
10
页