\(K=1\) の場合自明です。そうでないときを考えます。与えられた点の集合を \(S\) とします。

まず \(S\) の点 \(P\) を任意にとります。
「\(P\) を通り、\(P\) 以外の \(S\) の点を \(1\) つ以上通るような直線」全てについて、それぞれの直線の上に何個の点があるかを調べます。これは、\(S\) の各点 \(Q\) に対してベクトル \(\overrightarrow{PQ}\) を適当に正規化したものを数えることで \(O(N\log N)\) でできます。これにより、「\(P\) を通り、\(P\) 以外の \(S\) の点を \(1\) つ以上通るような直線」たちについて、\(S\) の点のうちちょうど \(k\) 個を通るものの個数を各 \(k\) で求めることができました。
\(S\) の他の点を \(P\) とした場合も同様に求め、それら全ての結果を合計したとき、\(S\) の点をちょうど \(k\) 個を通る直線はちょうど \(k\) 回カウントされます。したがって、それぞれ \(k\) で割ることで重複を取り除くことができます。

全体の計算量は \(O(N^2 \log N)\) です。

実装例(C++)