Line（双精度对）和Point（整数对）。HashMap<Line，List<Point>)
3.循环遍历所有点对，并针对每个点对：计算连接点的Line，并将该行与这些点添加到多映射中。在没有固定两个点的情况下，"Collinear"这个词并没有什么意义。因此，在我看来，“找到给定集合中所有共线的点”并不是很有意义，除非你固定了两个点并测试其他点是否共线。
也许一个更好的问题是，在给定的集合中最多有多少共线点？在这种情况下，你可以固定两个点（只需使用2个循环），然后遍历其他点，并检查固定点和其他点之间的斜率是否相同。你可以使用以下内容进行检查，假设坐标为整数（否则可以将参数类型更改为double）。
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Returns whether 3 points are collinear
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}
所以逻辑变成这样：
int best = 2;
for (int i = 0; i < number of points; ++i) {
for (int j = i+1, j < number of points; j++) {
int count = 2;
for (int k = 0; i < number of points; ++k) {
if (k==i || k==j)
continue;
check that points i, j and k are collinear (use function above), if so, increment count.
}
best = max(best,count);
}
}
在双重平面中解决问题，将所有点转换为线段。然后运行平面扫描以报告所有交点。双重平面中的线将通过相同点表示共线点。平面扫描可以在O(nlogn)时间内完成。
你确定对运行时的分析正确吗？你说要循环遍历所有点对，其数量为n*(n-1)/2，即O(n^2)。然后你将该线和点对添加到映射中。但是，我不认为添加这样一条线 + 点组合的时间是恒定的。这意味着总体上你的时间是O(n^2 log n)，而不是常数乘以n^2，这就是O(n^2)的意思。
所以真正的问题是，既然可以在O(n^2 log n)的时间内完成，那么能否在O(n^2)的时间内完成。显然，O(n^2)给出了下限，因为你必须至少打印出每个点对，其中有O(n^2)个。我的感觉是，这是一个完全普通的排序问题，人们无法期望比O(n^2 log n)更好的结果。然而，证明这个事实可能不容易。
另一个需要注意的问题是，该集合可能包含零个或一个点，因此您需要检查您的算法是否正确处理这些情况，否则编写专门处理它们的特殊情况。