一道数学题,一百分!http://hi.baidu.com/%C0%BC%D6%AE%B7%E7/blog/item/68d7c5fa5ec9f28c9e5146bf.html#comment
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/27 07:13:51
一道数学题,一百分!http://hi.baidu.com/%C0%BC%D6%AE%B7%E7/blog/item/68d7c5fa5ec9f28c9e5146bf.html#comment
一道数学题,一百分!
http://hi.baidu.com/%C0%BC%D6%AE%B7%E7/blog/item/68d7c5fa5ec9f28c9e5146bf.html#comment
一道数学题,一百分!http://hi.baidu.com/%C0%BC%D6%AE%B7%E7/blog/item/68d7c5fa5ec9f28c9e5146bf.html#comment
初始化损坏面积S=0.将所有的圆按照圆心位置先上后下、先左后右排好序,然后进行遍历：
对于圆心位置为(x,y)的圆,考察(x-1,y)、(x-1,y-1)、(x,y-1)这三处有没有其它圆存在(可见,一共只有
8种情况.考虑到对称性和重叠覆盖,包括零面积在内会出现5种可能的相交面积)
根据重叠的情况,S=S+单位圆面积-重复面积
对于某个单位圆与其它若干个圆重复面积的计算,通过扇形面积与三角形面积的加加减减即可得到,中学数学
内容,不再赘述.事先可将这些值算好,遍历的时候直接应用就可以了.
比如按照先上后下,先左后右的次序排序并遍历;
"对于圆心位置为(x,y)的圆,考察(x-1,y)、(x-1,y-1)、(x,y-1)这三处有没有其它圆存在"
有点遗漏,
应该是考察(x+1,y).(x-1,y-1),(x,y-1),(x+1,y-1)四个园,共16种情况;
1)预先求出这16种可能的情况下的圆的重叠面积,这步的复杂度为o(1);
2)排序的复杂度是o(nlogn);
3)遍历的复杂度是o(n),对每个圆查找其相交圆的复杂度为o(logn),所以该步的复杂度为o(nlogn)
这样总的复杂度应该是o(nlogn);
麻烦
1，(π-(π/3-（√3）/4))*2
2，因为n个圆的排列方式不同，所计算出的面积是不同的，计算思想同上……
3，说实话，很繁……你还是自己算吧~就是分割，然后计算面积……
1，两个圆时，损害面积为两个园的面积减去重叠部分，
而重叠部分面积为圆面积减去内接三角形面积在乘以2/3
计此面积为x
多个圆时，一样计算，有n个圆时，面积为n∏r平方-（n-1)x
麻烦