如何生成平面内任意三点不共线的 n 个点

关于这个问题，我很早之前我就问过了，可惜没有人给出较好的解答。

1、$n$ 个点，任意三个不共线

2、生成的 $n$ 个点比较随机分布

显然朴素的算法 $O(n^3)$，实际上期望生成 $10^5$ 左右个点，显然不可行。

考虑构造，可以在凸多边形上取端点，但是凸多边形的生成显然不太随机（起码目前我想到的算法），也就是不能保证点的随机性，虽然它是 $O(n)$ 的。

一种对暴力的优化就是优化查询不共线的过程，可以用一棵平衡树维护（如 $map$），每次可以 $O(nlogn)$ 查询并插入，时间上明显更优（跑个一天还是行的），但是空间炸裂。