用圆上的一组点来计数四边形的数目
设x^2 + y^2 = r^2是带r a实的圆。
首先，我得到了圆上的所有整数点(例如(1，2)，(-1，2)，(1，-2)，(-1，-2)，(2，1)，(-2，-1)，(2，- 1)，(-2，-1)，(-2，-1)，r=sqrt{5})。
我如何才能得到这些点上可能的四元数？
我所知道的唯一方法是用蛮力和测试所有可能的4个周期，删除那些有交叉边的循环，但是对于大r来说，它变得太大了。即使对于r=sqrt(5)，对于python也需要大约10秒的时间。
回答 2
Stack Overflow用户
发布于 2020-07-15 18:12:39
改变方法，从一个简单的问题开始：
给定一组位于圆上的点：
- ，如果这个尺寸是3，你能有多少个四边形？
- Easy: 0- ，如果尺寸是4，你能有多少四边形？
- Since the points lie on the same circle you will never have 3 points lying on the same straight line. So the answer is 1现在变得更难了
- ，如果尺寸是5，你能有多少个四边形？
- For 4 points we have just one quadrilateral: (p1, p2, p3, p4). Now I can replace each one of them with p5. The total is 5.- ，如果大小为n，你能有多少四元数？
- You can have as many quadrilaterals as the number of possible _combinations without repetitions_ of a set of n items in subsets of size 4, which is n!/(4!\*(n-4)!)你不需要知道什么坐标有点，但只需要知道有多少点。记住:给出3个不位于同一直线上的点，你只能有一个圆。无论你如何从一个圆中得到三个点，它们永远不会在同一条直线上躺着。这意味着无论你如何从一个圆中得到4个点，你都可以用它们来建立一个四边形。
Stack Overflow用户
发布于 2020-07-15 18:50:08
注意，一个圆上的任何4个点都形成一个四边形(例如，按cw顺序选择它们)。您只需找到所有属于pythogorean三元组的积分值，其中m^n + n^2 = r^2。
T = 0
for m = 1 ... r
for n = 1 ... r
if m*m + n*n = r*r
T++
N = 4*T // (+/-m, +/-n) points on circle
result = N > 0 ? (N choose 4) : 0 // all quads为了提高效率，可以去掉上面的内环(n^2 =地板(r^2- m^2))。
https://stackoverflow.com/questions/62920628
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号