计算用圆上的一组点可以组成的四边形的数量

Question

设 x^2 + y^2 = r^2 为圆，r 为实数。

首先我得到圆上的所有整数点（例如 (1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1 ), (-2, 1), (2, -1), (-2, -1) 对于 r=sqrt{5})

如何获得这些点可能的四边形数量？

我知道的唯一方法是暴力测试所有可能的 4 循环并删除具有交叉边缘的循环，但对于大 r 来说它变得太大了。即使对于 r=sqrt(5) python.

也需要大约 10 秒

Answer 1

换一种方式，从一个简单的问题开始：

给定圆上的一组点：

如果大小为3，你能有多少个四边形？
- 简单：0
如果大小为4，你能有多少个四边形？
- 因为这些点位于同一个圆上，所以永远不会有 3 个点位于同一条直线上。所以答案是 1

现在变得有点难了

如果大小为5，你可以有多少个四边形？
- 对于 4 个点，我们只有一个四边形：(p1, p2, p3, p4)。现在我可以用 p5 替换它们中的每一个。总数是5.
如果大小为n，你可以有多少个四边形？
- 四边形的数量与可能的不重复组合的数量一样多 大小为 4 的子集中的一组 n 项，即 n!/(4!* (n-4)!)

你不需要知道什么坐标有点，但知道有多少点。请记住：给定 3 个不在同一条直线上的点，您只能得到一个圆。无论你从一个圆中得到三个点，它们永远不会位于同一条直线上。这意味着无论你从一个圆中得到 4 个点，你都可以用它们来构建一个四边形

Answer 2

注意圆上的任意4个点构成一个四边形（比如顺时针选择）。你只需要找到所有的整数值勾股三元组，其中 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 = floor(r^2 - m^2))

计算用圆上的一组点可以组成的四边形的数量

Counting number of quadrilaterals that can be made with a set of points on a circle

algorithm

geometry

graph-algorithm