CropCircles问题能帮解决么,希望有源代码

被毁坏的玉米地(Crop Circles)

提交文件名：crop.exe

问题描述：

    “哈姆，外星人又在那了！”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前，他们的玉米地都会很奇怪的遭到毁坏(据埃塞说是外星人干的)。所有破坏的地方都是以 1 米为半径的圆。哈姆发现，如果玉米地上建立一个适当的直角坐标系的话，那些圆心的坐标将都为整数。万幸的是，埃塞和哈姆有玉米保险，但必须把损坏的面积统计出来。


 

输入格式：

    输入文件为当前目录下的文本文件“crop.dat”中。

    文件的第一行为一个整数n(0
输出格式：

    输出文件为当前目录下的“crop.out”。

    输出统计出的总面积，四舍五入到小数点后4位。(π=3.1415926535)

输入输出样例：

输入样例一
 输入样例二
 
crop.dat crop.out
 crop.dat
 crop.out
 
2

0 0

1 0
 5.0548
 3

5 9

5 8

6 9
 6.8402
 

11 个解决方案

#1

---

初始化损坏面积S=0。将所有的圆按照圆心位置先上后下、先左后右排好序，然后进行遍历：
对于圆心位置为(x,y)的圆，考察(x-1,y)、(x-1,y-1)、(x,y-1)这三处有没有其它圆存在(可见，一共只有
8种情况。考虑到对称性和重叠覆盖，包括零面积在内会出现5种可能的相交面积)
根据重叠的情况，S=S+单位圆面积-重复面积

对于某个单位圆与其它若干个圆重复面积的计算，通过扇形面积与三角形面积的加加减减即可得到，中学数学
内容，不再赘述。事先可将这些值算好，遍历的时候直接应用就可以了。

#2

---

这种题有没有使用大学里的数学知识使解题方式更简单!

#3

---

估计是哪里正在进行的竞赛，大家还是过一周之后再讨论这个问题吧

#4

---

而这个问题显然可以用O(n^3)的算法解决。而且我感觉可以用O(n^2log(n))算法解决

#5

---

能指点一下吗?

#6

---

我已经用matlab解决了，呵呵

#7

---

dlyme的方法就可以了呀;

比如按照先上后下,先左后右的次序排序并遍历;
"对于圆心位置为(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);

#8

---

是的，应该是四个圆，上面和左面的都得考虑。

好像是什么竞赛题，最近几个人问这个问题了。

#9

---

这个题目中半径固定为1那就更加简单了，我原先还一位半径也可以任意。

#10

---

是广东OI2001年的复试题，但找不到结题报告。。。

#11

---

组合数学的方法只能解决一种情况

对于非单位圆的面积重叠计算不是很懂。。。