如何随机生成任意三个点都不共线的 N 个点?
  • 板块灌水区
  • 楼主xiejinhao
  • 当前回复12
  • 已保存回复12
  • 发布时间2020/6/26 23:23
  • 上次更新2023/11/7 00:01:25
查看原帖
如何随机生成任意三个点都不共线的 N 个点?
196649
xiejinhao楼主2020/6/26 23:23

1、RT,最暴力的方法肯定是 O(n3)O(n^3) 暴力搞,空间是 O(n)O(n)的;

2、后面想出了一种优化,即把任意两个向量扔到一个可以维护的数据结构中(如平衡树),然后每生成一个点去查询否有斜率相同的向量,时间是 O(n2log n)O(n^2\text{log }n),空间 O(n2)O(n^2)

问:是否有更高效的算法。

2020/6/26 23:23
加载中...