c - 同じライン上のポイントの最大数を決定する方法は?

Question

与えられた: それぞれが一意の座標 (x _i ,y _i )を持つ多くの点

出力: 同一ライン上のポイントの最大数

これは私の方法です：

for i=1..n
    for j=i..n
        get the line determined by point[i] and point[j]
        for k=1..n
            check if point[k] is on this line

しかし、この方法は時間がかかりすぎて、OJ システムの制限時間を常に超えているようです。

Answer 1

各ポイントを繰り返し、他の各ポイントの極角を計算し、極角を並べ替えます

このコスト O(n^2*lgn)

Answer 2

私はこれを実装していませんが、O（n）で実装できるかもしれません。

• ハッシュマップを使用して、極角でポイントを保存します。Map<Double,List<Point>>、ここDoubleで、は角度です

• List<Point>次に、最大長でを追跡しながら、マップを繰り返します。そのリストには結果が含まれます。

それで遊んでください。動作するようです。