这是一个interview question：“查找给定集合中的所有共线点”。
据我所知，他们要求打印出位于同一直线上的点（每两点总是共线）。我建议如下。
让我们介绍两种类型Line（双精度对）和Point（整数对）。
创建多重映射：HashMap<Line, List<Point>)
对所有点对和每对点进行循环：计算连接点的Line，并将带有这些点的线添加到多重映射中。
最后，多重映射包含作为关键点的线和作为其值的每条线的列表共线点。
复杂性为O（n ^ 2）。有意义吗？有更好的解决方案吗？
最佳答案
共线在这里没有真正意义，除非你确定2点开始。所以说，“在给定的集合中找到所有共线点”在我看来没有多大意义，除非你确定2个点并测试其他点，看看它们是否共线。
也许更好的问题是，给定集合中共线点的最大数目是多少？在这种情况下，可以固定在2个点上（仅使用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);
}
}