有什么好的算法没有？如果是先算一个，算第二个的时候发现与之前的任意圆相交就重算的话，总觉得效率太低了。
32 个解决方案
#1
把圆形考虑成矩形....
#2
效率取决于你判断圆相交的算法
#3
把圆形考虑成矩形....
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个方法感觉好像要好点吧。可以不可以这样考虑：
先生成一个圆。然后顺便对应生成一个rect。在下边生成一个圆的圆心的时候，point（圆心）.x-radius或者point（圆心）.y-radius如果在上次生成的rect里边就pass生成下一个。
这样会遗漏一些点。比如两个圆接近相切的时候就会不满足条件。不知道会不会满足楼主要求？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个方法感觉好像要好点吧。可以不可以这样考虑：
先生成一个圆。然后顺便对应生成一个rect。在下边生成一个圆的圆心的时候，point（圆心）.x-radius或者point（圆心）.y-radius如果在上次生成的rect里边就pass生成下一个。
这样会遗漏一些点。比如两个圆接近相切的时候就会不满足条件。不知道会不会满足楼主要求？
#4
判断二圆心的距离是否大于等于二倍的半径。
#5
判断二圆心的距离是否大于等于二倍的半径
#6
我就是觉得，不满足条件，再找下一个效率太低，比如圆比较大的情况，这样就要找很多次，才能找到下一个合适的圆心
#7
请问楼主什么语言啊？才5个圆，重算也不是很费时啊，一般做20个左右的随机而已啊
#8
矩形的长宽和圆的半径是运行时输入的。
如果输入的长宽和半径都很大，刚刚好只能容纳5个圆的话，程序陷入长时间无响应都有可能吧？
如果输入的长宽和半径都很大，刚刚好只能容纳5个圆的话，程序陷入长时间无响应都有可能吧？
#9
先放置五个圆,删除与其他圆重叠且后生成那些的圆,重画.应该省写事,不过判断的次数好象没减少.还可以放置多个圆,删除重叠的几个,感觉在冒险啊.就想了这点,不知有没有用!!!!!!!
#10
楼上这不是换汤不换药么，原理和效率都与“相交则重找”一样。
感觉这个问题是有点难，真不知道怎么解决比较好……
感觉这个问题是有点难，真不知道怎么解决比较好……
#11
才五个圆，效率有意义吗？
#12
LiChenYue(李忱悦，每一次喊你，在我心！暗恋未遂，独孤求偶！)
才五个圆，效率有意义吗？
--------------------------------------------
五个圆，多是不多，但重点是想学到一个好的算法……
才五个圆，效率有意义吗？
--------------------------------------------
五个圆，多是不多，但重点是想学到一个好的算法……
#13
圆不是有半径吗，计算两个圆心之间的距离，如果小于圆的半径和那就是相交了。
#14
判断二圆心的距离是否大于等于二倍的半径。
不知lz对算法效率有什么特殊要求不.如果看作矩形会漏掉一部分可行分布
不知lz对算法效率有什么特殊要求不.如果看作矩形会漏掉一部分可行分布
#15
我不是不知道怎么判断相交，我是觉得如果取得的第n个圆如果与之前的圆相交，要重算，这样效率不高。
圆的半径较小时重算次数倒是不多，但如果圆的半径很大，而矩形相对较小，这样重算的次数就会很多……
圆的半径较小时重算次数倒是不多，但如果圆的半径很大，而矩形相对较小，这样重算的次数就会很多……
#16
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
#17
我觉得还是用半径的那种方法最有效
#18
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
#19
cmen(cmen)
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
--------------------------------------------------------------------
chehw(chehw)
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
------------------------------------------------------------------------
如果是从一个数组里面随机找出5个数的话，这个方法的确是很快的。每次找到一个数，只用江最后一个元素移到当前找到的位置，然后认为数组大小减一，继续找下一个就可以了。
但现在这是一个平面范围，每次找到一个圆，就要将n个点的坐标从数组之类的集合里面删除，就要执行很多操作。
或许从效率上讲还没有重找的效率高吧？
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
--------------------------------------------------------------------
chehw(chehw)
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
------------------------------------------------------------------------
如果是从一个数组里面随机找出5个数的话，这个方法的确是很快的。每次找到一个数，只用江最后一个元素移到当前找到的位置，然后认为数组大小减一，继续找下一个就可以了。
但现在这是一个平面范围，每次找到一个圆，就要将n个点的坐标从数组之类的集合里面删除，就要执行很多操作。
或许从效率上讲还没有重找的效率高吧？
#20
顶w_anthony()
#21
学习
#22
通过优化步骤（2），应该是非常高效的算法。
你可以把一维数组看成是一个二维的矩陈（与矩形相对应）
设"判断二圆心的距离是否大于等于二倍的半径"的执行时间为t
设数组下标为i, 则i/(m-r),i/(n-r)对应于矩形内的点（x,y)
利用"判断二圆心的距离是否大于等于二倍的半径"的方法，可以迅速将所有2倍半径以内的点全部置1(还可进一步优化：利用内切矩形的方法使置1的时间固定为(sqrt(2)-1)r*t。)。
若圆很小，矩形很大，则重找的方法应是最高效的。
若圆和矩形均很大,设共有N个点，用重找的方法的平均需(N/2)*t才能找到下一个圆心，且不能判断是否已无解。由于r远远小于N，因此"重找"法劣于"置1"的方法。
你可以把一维数组看成是一个二维的矩陈（与矩形相对应）
设"判断二圆心的距离是否大于等于二倍的半径"的执行时间为t
设数组下标为i, 则i/(m-r),i/(n-r)对应于矩形内的点（x,y)
利用"判断二圆心的距离是否大于等于二倍的半径"的方法，可以迅速将所有2倍半径以内的点全部置1(还可进一步优化：利用内切矩形的方法使置1的时间固定为(sqrt(2)-1)r*t。)。
若圆很小，矩形很大，则重找的方法应是最高效的。
若圆和矩形均很大,设共有N个点，用重找的方法的平均需(N/2)*t才能找到下一个圆心，且不能判断是否已无解。由于r远远小于N，因此"重找"法劣于"置1"的方法。
#23
哎，我先提出来的东西，被人家解释了一下，估计分数至少得平分了
上次回答问题写了一大堆东西，发现比楼上晚了10秒，结果一分也没有，虽然提的东西一样。
伤心。。。
关于效率问题，你不用考虑得太多。这样做的效率肯定要比你盲目的重找高得多。因为这样的方法至少能保证只要有点可以做为圆心，就一定能够找得到。每次循环都能保证找到一个圆心，否则就结束。也就是算法必备的 有穷性。
关于置一的方法，你可以不用每次都判断每个点是否都与当前圆心的距离在两倍半径之内。你可以之前做一个半径为2r的模板，模板的2r范围内的点都置一，其他为零。每次置一的时候只需要以当前圆心为中心的矩形与模板做一个 或 运算即可。这样可以节省大量的比较，代价就是内存中保存这么一个模板。即 空间换时间。
上次回答问题写了一大堆东西，发现比楼上晚了10秒，结果一分也没有，虽然提的东西一样。
伤心。。。
关于效率问题，你不用考虑得太多。这样做的效率肯定要比你盲目的重找高得多。因为这样的方法至少能保证只要有点可以做为圆心，就一定能够找得到。每次循环都能保证找到一个圆心，否则就结束。也就是算法必备的 有穷性。
关于置一的方法，你可以不用每次都判断每个点是否都与当前圆心的距离在两倍半径之内。你可以之前做一个半径为2r的模板，模板的2r范围内的点都置一，其他为零。每次置一的时候只需要以当前圆心为中心的矩形与模板做一个 或 运算即可。这样可以节省大量的比较，代价就是内存中保存这么一个模板。即 空间换时间。
#24
谢谢楼上两位的解释。
不过在chehw(chehw)所说的矩阵中即使配合“置一”找到一个合适的点也不是O(1)的时间吧？如果放到一位数组里面，从第一次找到圆中挖掉两倍半径的区域倒还简单，但执行几次后，挖掉后找出的圆的两倍半径的点就不是那么容易了。
至于cmen(cmen)的所说的模板相或的做法，倒是不错的想法，挖点的时候可以快很多。但是如果不知道如何在挖过点剩下的区域快速的找到一个合适的点，这个问题还是不好解决阿。总不能每次都把剩下的点先写到一维数组里面，再用随机数去取一个合适的点吧？
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
不过在chehw(chehw)所说的矩阵中即使配合“置一”找到一个合适的点也不是O(1)的时间吧？如果放到一位数组里面，从第一次找到圆中挖掉两倍半径的区域倒还简单，但执行几次后，挖掉后找出的圆的两倍半径的点就不是那么容易了。
至于cmen(cmen)的所说的模板相或的做法，倒是不错的想法，挖点的时候可以快很多。但是如果不知道如何在挖过点剩下的区域快速的找到一个合适的点，这个问题还是不好解决阿。总不能每次都把剩下的点先写到一维数组里面，再用随机数去取一个合适的点吧？
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
#25
执行第n次与执行第1次的方法完全一样，用不着挖掉什么，不用管原有已置1的点,将它继续置1就可以了。
#26
把圆看成点。
#27
先把这五个圆放按顺序到矩形中
让后就开始若干次布尔运动。。。。
让后就开始若干次布尔运动。。。。
#28
To chehw(chehw),置完一后，你怎么取下一个圆心坐标？那些可以取的标记为0的点，在内存里可并不是连续的阿。
To zswang，随机运动的效率不知如何，感觉也不比“重找”好。因为每次运动都要判断行进方向，计算下一个点，是否碰撞等等……
To zswang，随机运动的效率不知如何，感觉也不比“重找”好。因为每次运动都要判断行进方向，计算下一个点，是否碰撞等等……
#29
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
-------------------------------------------------------------------
“重找”不是效率的问题，如果没解，它可能陷入死循环
如果存在解，“置一”与“重找”的效率不一定谁高：如果圆的半径很大，那么“重找”的效率肯定很低，而且随着已确定的圆心的数目增多，需要比较的次数也越来越多。如果半径很小，比如半径为1，即每次只找一个点，那么“重找”的效率可能会很高。而“置一”的方法根本不存在这样的问题，无论以确定了多少个圆心，确定下一个圆心所需的计算量是固定的（如果不是更少）。就像一个O(N) 和 100 个O(1) 一样，当实际中N比较小的时候，运行时间很可能是O(N)的短。
至于如何在挖过点剩下的区域快速的找到一个合适的点，你可以每次用遍历搜索的方法，从二维数组中顺次找出随机数对应的圆心。你也可以记录每一行（或若干行，或若干列）中有效的点的个数，这样可以迅速定位到圆心所在的行，只在该行内遍历搜索即可。这样可以大大减少每次需要遍历的点，代价是保存每一行的有效点数。如果模板建立好了，更新这个值也很容易。类似于树的分层概念，最优的效率是O(logN),N为可用点的个数
-------------------------------------------------------------------
“重找”不是效率的问题，如果没解，它可能陷入死循环
如果存在解，“置一”与“重找”的效率不一定谁高：如果圆的半径很大，那么“重找”的效率肯定很低，而且随着已确定的圆心的数目增多，需要比较的次数也越来越多。如果半径很小，比如半径为1，即每次只找一个点，那么“重找”的效率可能会很高。而“置一”的方法根本不存在这样的问题，无论以确定了多少个圆心，确定下一个圆心所需的计算量是固定的（如果不是更少）。就像一个O(N) 和 100 个O(1) 一样，当实际中N比较小的时候，运行时间很可能是O(N)的短。
至于如何在挖过点剩下的区域快速的找到一个合适的点，你可以每次用遍历搜索的方法，从二维数组中顺次找出随机数对应的圆心。你也可以记录每一行（或若干行，或若干列）中有效的点的个数，这样可以迅速定位到圆心所在的行，只在该行内遍历搜索即可。这样可以大大减少每次需要遍历的点，代价是保存每一行的有效点数。如果模板建立好了，更新这个值也很容易。类似于树的分层概念，最优的效率是O(logN),N为可用点的个数
#30
个人感觉只要不是半径太大，或者要确定的圆的数目太多的话，重找肯定要快很多；但如果半径一大的话，为了确保能找到合适的圆心，还是用置一保险一点。
置一主要是被过多赋值操作和遍历拖累了。试想一下，第一次确定一个圆后，在运气不济的情况下，取到的随机数刚好都落在这个圆的范围内，并且每个点一次（先不考虑重复）的话，由于取点是O(1)的，所以也只是计算圆的面积大小个点的次数。而置一的话，不论如何，都要进行这么多次操作。再根据经验，一般来说，重找的话不会运气背到全落在那个圆的范围内这种事。所以认为大多数情况还是重找好一点。
可能这个问题没有绝对最高效的算法，要根据矩形长宽和圆的半径的比值来确定算法吧？
再放几天，看看有没有更好的方法……
置一主要是被过多赋值操作和遍历拖累了。试想一下，第一次确定一个圆后，在运气不济的情况下，取到的随机数刚好都落在这个圆的范围内，并且每个点一次（先不考虑重复）的话，由于取点是O(1)的，所以也只是计算圆的面积大小个点的次数。而置一的话，不论如何，都要进行这么多次操作。再根据经验，一般来说，重找的话不会运气背到全落在那个圆的范围内这种事。所以认为大多数情况还是重找好一点。
可能这个问题没有绝对最高效的算法，要根据矩形长宽和圆的半径的比值来确定算法吧？
再放几天，看看有没有更好的方法……
#31
没有学习
#32
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
----------------------------------------------------------------
“置一”有个排除过程，“重找”没有
----------------------------------------------------------------
“置一”有个排除过程，“重找”没有
#1
把圆形考虑成矩形....
#2
效率取决于你判断圆相交的算法
#3
把圆形考虑成矩形....
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个方法感觉好像要好点吧。可以不可以这样考虑：
先生成一个圆。然后顺便对应生成一个rect。在下边生成一个圆的圆心的时候，point（圆心）.x-radius或者point（圆心）.y-radius如果在上次生成的rect里边就pass生成下一个。
这样会遗漏一些点。比如两个圆接近相切的时候就会不满足条件。不知道会不会满足楼主要求？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个方法感觉好像要好点吧。可以不可以这样考虑：
先生成一个圆。然后顺便对应生成一个rect。在下边生成一个圆的圆心的时候，point（圆心）.x-radius或者point（圆心）.y-radius如果在上次生成的rect里边就pass生成下一个。
这样会遗漏一些点。比如两个圆接近相切的时候就会不满足条件。不知道会不会满足楼主要求？
#4
判断二圆心的距离是否大于等于二倍的半径。
#5
判断二圆心的距离是否大于等于二倍的半径
#6
我就是觉得，不满足条件，再找下一个效率太低，比如圆比较大的情况，这样就要找很多次，才能找到下一个合适的圆心
#7
请问楼主什么语言啊？才5个圆，重算也不是很费时啊，一般做20个左右的随机而已啊
#8
矩形的长宽和圆的半径是运行时输入的。
如果输入的长宽和半径都很大，刚刚好只能容纳5个圆的话，程序陷入长时间无响应都有可能吧？
如果输入的长宽和半径都很大，刚刚好只能容纳5个圆的话，程序陷入长时间无响应都有可能吧？
#9
先放置五个圆,删除与其他圆重叠且后生成那些的圆,重画.应该省写事,不过判断的次数好象没减少.还可以放置多个圆,删除重叠的几个,感觉在冒险啊.就想了这点,不知有没有用!!!!!!!
#10
楼上这不是换汤不换药么，原理和效率都与“相交则重找”一样。
感觉这个问题是有点难，真不知道怎么解决比较好……
感觉这个问题是有点难，真不知道怎么解决比较好……
#11
才五个圆，效率有意义吗？
#12
LiChenYue(李忱悦，每一次喊你，在我心！暗恋未遂，独孤求偶！)
才五个圆，效率有意义吗？
--------------------------------------------
五个圆，多是不多，但重点是想学到一个好的算法……
才五个圆，效率有意义吗？
--------------------------------------------
五个圆，多是不多，但重点是想学到一个好的算法……
#13
圆不是有半径吗，计算两个圆心之间的距离，如果小于圆的半径和那就是相交了。
#14
判断二圆心的距离是否大于等于二倍的半径。
不知lz对算法效率有什么特殊要求不.如果看作矩形会漏掉一部分可行分布
不知lz对算法效率有什么特殊要求不.如果看作矩形会漏掉一部分可行分布
#15
我不是不知道怎么判断相交，我是觉得如果取得的第n个圆如果与之前的圆相交，要重算，这样效率不高。
圆的半径较小时重算次数倒是不多，但如果圆的半径很大，而矩形相对较小，这样重算的次数就会很多……
圆的半径较小时重算次数倒是不多，但如果圆的半径很大，而矩形相对较小，这样重算的次数就会很多……
#16
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
#17
我觉得还是用半径的那种方法最有效
#18
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
#19
cmen(cmen)
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
--------------------------------------------------------------------
chehw(chehw)
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
------------------------------------------------------------------------
如果是从一个数组里面随机找出5个数的话，这个方法的确是很快的。每次找到一个数，只用江最后一个元素移到当前找到的位置，然后认为数组大小减一，继续找下一个就可以了。
但现在这是一个平面范围，每次找到一个圆，就要将n个点的坐标从数组之类的集合里面删除，就要执行很多操作。
或许从效率上讲还没有重找的效率高吧？
1 把矩形考虑成矩阵A，初始时都为1，表示每个点都可以做为圆心
2 根据圆的半径，得到实际可以做为圆心的矩形范围A'（矩形四边向内收缩半径宽度）
3 根据A'的大小（Height*Weight个点)随机生成一个圆心
4 若已达到圆心个数要求（5个），则结束，否则转5
5 将这个点及其2倍半径范围内的A'元素值置为0，表示这些点不能再被置为圆心（否则会相交）
6 重新计算A'的大小，并在此范围内随机生成圆心。转4
这只是一种贪婪的寻找方法，并不保证一定能够找到满足要求的5个圆心，即使解确实存在
--------------------------------------------------------------------
chehw(chehw)
假设矩形长宽分别为m,n，圆的半径为r
(1)定义一个BYTE bCenter[(m-r)*(n-r)]; 并将所有元素置0表示可以该点可以放置圆心。
(2)每生成一个圆后，要将以该圆心中心，2r为半径内的所有点均置1，表示不能放置新圆。同时计算bCenter为1的元素个数(k), 若k==(m-r)*(n-r)则中止。
(3)用rand()%((m-r)*(n-r)-k)来生成下一个圆的圆心位置，若已有五个圆，则中止；否则返回至(2)。
------------------------------------------------------------------------
如果是从一个数组里面随机找出5个数的话，这个方法的确是很快的。每次找到一个数，只用江最后一个元素移到当前找到的位置，然后认为数组大小减一，继续找下一个就可以了。
但现在这是一个平面范围，每次找到一个圆，就要将n个点的坐标从数组之类的集合里面删除，就要执行很多操作。
或许从效率上讲还没有重找的效率高吧？
#20
顶w_anthony()
#21
学习
#22
通过优化步骤（2），应该是非常高效的算法。
你可以把一维数组看成是一个二维的矩陈（与矩形相对应）
设"判断二圆心的距离是否大于等于二倍的半径"的执行时间为t
设数组下标为i, 则i/(m-r),i/(n-r)对应于矩形内的点（x,y)
利用"判断二圆心的距离是否大于等于二倍的半径"的方法，可以迅速将所有2倍半径以内的点全部置1(还可进一步优化：利用内切矩形的方法使置1的时间固定为(sqrt(2)-1)r*t。)。
若圆很小，矩形很大，则重找的方法应是最高效的。
若圆和矩形均很大,设共有N个点，用重找的方法的平均需(N/2)*t才能找到下一个圆心，且不能判断是否已无解。由于r远远小于N，因此"重找"法劣于"置1"的方法。
你可以把一维数组看成是一个二维的矩陈（与矩形相对应）
设"判断二圆心的距离是否大于等于二倍的半径"的执行时间为t
设数组下标为i, 则i/(m-r),i/(n-r)对应于矩形内的点（x,y)
利用"判断二圆心的距离是否大于等于二倍的半径"的方法，可以迅速将所有2倍半径以内的点全部置1(还可进一步优化：利用内切矩形的方法使置1的时间固定为(sqrt(2)-1)r*t。)。
若圆很小，矩形很大，则重找的方法应是最高效的。
若圆和矩形均很大,设共有N个点，用重找的方法的平均需(N/2)*t才能找到下一个圆心，且不能判断是否已无解。由于r远远小于N，因此"重找"法劣于"置1"的方法。
#23
哎，我先提出来的东西，被人家解释了一下，估计分数至少得平分了
上次回答问题写了一大堆东西，发现比楼上晚了10秒，结果一分也没有，虽然提的东西一样。
伤心。。。
关于效率问题，你不用考虑得太多。这样做的效率肯定要比你盲目的重找高得多。因为这样的方法至少能保证只要有点可以做为圆心，就一定能够找得到。每次循环都能保证找到一个圆心，否则就结束。也就是算法必备的 有穷性。
关于置一的方法，你可以不用每次都判断每个点是否都与当前圆心的距离在两倍半径之内。你可以之前做一个半径为2r的模板，模板的2r范围内的点都置一，其他为零。每次置一的时候只需要以当前圆心为中心的矩形与模板做一个 或 运算即可。这样可以节省大量的比较，代价就是内存中保存这么一个模板。即 空间换时间。
上次回答问题写了一大堆东西，发现比楼上晚了10秒，结果一分也没有，虽然提的东西一样。
伤心。。。
关于效率问题，你不用考虑得太多。这样做的效率肯定要比你盲目的重找高得多。因为这样的方法至少能保证只要有点可以做为圆心，就一定能够找得到。每次循环都能保证找到一个圆心，否则就结束。也就是算法必备的 有穷性。
关于置一的方法，你可以不用每次都判断每个点是否都与当前圆心的距离在两倍半径之内。你可以之前做一个半径为2r的模板，模板的2r范围内的点都置一，其他为零。每次置一的时候只需要以当前圆心为中心的矩形与模板做一个 或 运算即可。这样可以节省大量的比较，代价就是内存中保存这么一个模板。即 空间换时间。
#24
谢谢楼上两位的解释。
不过在chehw(chehw)所说的矩阵中即使配合“置一”找到一个合适的点也不是O(1)的时间吧？如果放到一位数组里面，从第一次找到圆中挖掉两倍半径的区域倒还简单，但执行几次后，挖掉后找出的圆的两倍半径的点就不是那么容易了。
至于cmen(cmen)的所说的模板相或的做法，倒是不错的想法，挖点的时候可以快很多。但是如果不知道如何在挖过点剩下的区域快速的找到一个合适的点，这个问题还是不好解决阿。总不能每次都把剩下的点先写到一维数组里面，再用随机数去取一个合适的点吧？
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
不过在chehw(chehw)所说的矩阵中即使配合“置一”找到一个合适的点也不是O(1)的时间吧？如果放到一位数组里面，从第一次找到圆中挖掉两倍半径的区域倒还简单，但执行几次后，挖掉后找出的圆的两倍半径的点就不是那么容易了。
至于cmen(cmen)的所说的模板相或的做法，倒是不错的想法，挖点的时候可以快很多。但是如果不知道如何在挖过点剩下的区域快速的找到一个合适的点，这个问题还是不好解决阿。总不能每次都把剩下的点先写到一维数组里面，再用随机数去取一个合适的点吧？
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
#25
执行第n次与执行第1次的方法完全一样，用不着挖掉什么，不用管原有已置1的点,将它继续置1就可以了。
#26
把圆看成点。
#27
先把这五个圆放按顺序到矩形中
让后就开始若干次布尔运动。。。。
让后就开始若干次布尔运动。。。。
#28
To chehw(chehw),置完一后，你怎么取下一个圆心坐标？那些可以取的标记为0的点，在内存里可并不是连续的阿。
To zswang，随机运动的效率不知如何，感觉也不比“重找”好。因为每次运动都要判断行进方向，计算下一个点，是否碰撞等等……
To zswang，随机运动的效率不知如何，感觉也不比“重找”好。因为每次运动都要判断行进方向，计算下一个点，是否碰撞等等……
#29
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
-------------------------------------------------------------------
“重找”不是效率的问题，如果没解，它可能陷入死循环
如果存在解，“置一”与“重找”的效率不一定谁高：如果圆的半径很大，那么“重找”的效率肯定很低，而且随着已确定的圆心的数目增多，需要比较的次数也越来越多。如果半径很小，比如半径为1，即每次只找一个点，那么“重找”的效率可能会很高。而“置一”的方法根本不存在这样的问题，无论以确定了多少个圆心，确定下一个圆心所需的计算量是固定的（如果不是更少）。就像一个O(N) 和 100 个O(1) 一样，当实际中N比较小的时候，运行时间很可能是O(N)的短。
至于如何在挖过点剩下的区域快速的找到一个合适的点，你可以每次用遍历搜索的方法，从二维数组中顺次找出随机数对应的圆心。你也可以记录每一行（或若干行，或若干列）中有效的点的个数，这样可以迅速定位到圆心所在的行，只在该行内遍历搜索即可。这样可以大大减少每次需要遍历的点，代价是保存每一行的有效点数。如果模板建立好了，更新这个值也很容易。类似于树的分层概念，最优的效率是O(logN),N为可用点的个数
-------------------------------------------------------------------
“重找”不是效率的问题，如果没解，它可能陷入死循环
如果存在解，“置一”与“重找”的效率不一定谁高：如果圆的半径很大，那么“重找”的效率肯定很低，而且随着已确定的圆心的数目增多，需要比较的次数也越来越多。如果半径很小，比如半径为1，即每次只找一个点，那么“重找”的效率可能会很高。而“置一”的方法根本不存在这样的问题，无论以确定了多少个圆心，确定下一个圆心所需的计算量是固定的（如果不是更少）。就像一个O(N) 和 100 个O(1) 一样，当实际中N比较小的时候，运行时间很可能是O(N)的短。
至于如何在挖过点剩下的区域快速的找到一个合适的点，你可以每次用遍历搜索的方法，从二维数组中顺次找出随机数对应的圆心。你也可以记录每一行（或若干行，或若干列）中有效的点的个数，这样可以迅速定位到圆心所在的行，只在该行内遍历搜索即可。这样可以大大减少每次需要遍历的点，代价是保存每一行的有效点数。如果模板建立好了，更新这个值也很容易。类似于树的分层概念，最优的效率是O(logN),N为可用点的个数
#30
个人感觉只要不是半径太大，或者要确定的圆的数目太多的话，重找肯定要快很多；但如果半径一大的话，为了确保能找到合适的圆心，还是用置一保险一点。
置一主要是被过多赋值操作和遍历拖累了。试想一下，第一次确定一个圆后，在运气不济的情况下，取到的随机数刚好都落在这个圆的范围内，并且每个点一次（先不考虑重复）的话，由于取点是O(1)的，所以也只是计算圆的面积大小个点的次数。而置一的话，不论如何，都要进行这么多次操作。再根据经验，一般来说，重找的话不会运气背到全落在那个圆的范围内这种事。所以认为大多数情况还是重找好一点。
可能这个问题没有绝对最高效的算法，要根据矩形长宽和圆的半径的比值来确定算法吧？
再放几天，看看有没有更好的方法……
置一主要是被过多赋值操作和遍历拖累了。试想一下，第一次确定一个圆后，在运气不济的情况下，取到的随机数刚好都落在这个圆的范围内，并且每个点一次（先不考虑重复）的话，由于取点是O(1)的，所以也只是计算圆的面积大小个点的次数。而置一的话，不论如何，都要进行这么多次操作。再根据经验，一般来说，重找的话不会运气背到全落在那个圆的范围内这种事。所以认为大多数情况还是重找好一点。
可能这个问题没有绝对最高效的算法，要根据矩形长宽和圆的半径的比值来确定算法吧？
再放几天，看看有没有更好的方法……
#31
没有学习
#32
个人感觉，大多数情况下，“重找”的赋值次数要远小于“置一”，比较次数可能会比“置一”多一些，但总体上还是觉得“置一”的效率不如“重找”。
----------------------------------------------------------------
“置一”有个排除过程，“重找”没有
----------------------------------------------------------------
“置一”有个排除过程，“重找”没有