搜索哪些点共线

hbghlyj

TSC999 发表于 2022-4-13 03:00
给定一个几何图形，这软件能搜索出哪些线段相等，哪些角度相等，哪些三角形全等，哪些三角形相似，........

编程作业3-共线点
编写一个程序来识别给定点集中的直线。

每个程序应将输入文件的名称作为命令行参数，读取输入文件（格式如下所述），将发现的线段打印到标准输出（格式如下所述），并将发现的线段绘制到标准绘图中（格式如下所述）。以下是API

   public class Brute {
       public static void main(String[] args)
   }
   
public class Fast {
    public static void main(String[] args)
}
输入格式
从输入文件中读取点，格式如下：一个整数N，后跟N对整数（x, y），每个整数在0到32,767之间。以下是两个示例。

% more input6.txt       % more input8.txt
6                       8
19000  10000             10000      0
18000  10000                 0  10000
32000  10000              3000   7000
21000  10000              7000   3000
1234   5678             20000  21000
14000  10000              3000   4000
                         14000  15000
                          6000   7000

输出格式
将程序发现的线段打印到标准输出，每行一个。将每个线段打印为其组成点的有序序列，用“ -> ”分隔。

1. % java Brute input6.txt
2. (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000)
3. (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (32000, 10000)
4. (14000, 10000) -> (18000, 10000) -> (21000, 10000) -> (32000, 10000)
5. (14000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)
6. (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)
8. % java Brute input8.txt
9. (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000)
10. (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000)
12. % java Fast input6.txt
13. (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)
15. % java Fast input8.txt
16. (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000)
17. (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000)

Copy the Code

hbghlyj

暴力代码是一个嵌套循环结构，它遍历点列表以找到共线点。让我们分析一下时间复杂度：
外循环（i循环）：从0运行到n-4（大约n次）。
第二循环（j循环）：从i+1运行到n-3（外循环每次迭代大约n次）。
第三循环（k循环）：从j+1运行到n-2（第二循环每次迭代大约n次）。
最内循环（l循环）：从k+1运行到n-1（第三循环每次迭代大约n次）。
由于每个循环大约运行 n 次，因此总体时间复杂度是所有​​四个循环复杂度的乘积：
\[ O(n) \times O(n) \times O(n) \times O(n) = O(n^4)\]
因此，暴力搜索代码的时间复杂度为 \( O(n^4) \)。

hbghlyj

现在让我们分析更快代码（按斜率排序）的时间复杂度，看看为什么它更快

外循环
for (int i = 0; i < n - 1; i++) {
...
}
此循环运行 n-1 次，因此其复杂度为 O(n)。

在外循环内部，首先执行
对点进行排序
Arrays.sort(points);
Arrays.sort(points, points[i].SLOPE_ORDER);
每个排序操作的时间复杂度为 O(n log n)。所以合并起来仍然是 O(n log n) + O(n log n) = O(n log n)。

然后是内循环
for (int j = 2; j < n; j++) {
...
}
这个循环运行 n-2 次，所以它的复杂度是 O(n)。

总之，我们得到更快代码的时间复杂度是 O(n) * (O(n log n) + O(n)) = O(n^2 log n)。