给定一个包含n个无重复点的有限集P,设计一个算法,验证是否满足任意三点属于P,使三点组成的三角形面积均大于零(即P中任意三点不共线),要求算法时间复杂度低于O((n^2)logn),若满足则返回true,否则返回false

5 2 收藏


直接登录
最新评论
  • nobel8 工程师 2016/05/06

    百度吧

  • 实际上是任意找两点划出一条线,生成这条线在x-y坐标系上的函数 y=f(x),形式为kx+a。

    记下这个函数的(k,a)值,当任意两点生成的k,a在记下的集合里找到了,说明出现了3点一线的情况。

    生成所有的k,a复杂度为O(n^2)  — n*(n-1)

     

    接下来就是k,a集合如何组织和查找。

    用二叉平衡树满,查找时间是lg(n) — 这里可以勉强算小于,因为前期k,a数量不多,查找也就达不到 lg(n)
    hash表 — 尝试不同的hash算法,解决需要多少空间,以及key冲突的问题,查找 O(1)
    可以尝试结合hash表和二叉平衡树
    困了,不想了,有兴趣的继续,啦啦啦。。。

    • Hastings   2016/05/07

      你好,能不能把你第二段结合二叉树的思路讲一下?我当时做的想法是建立两层for循环,第一层初始化一个空数组作为哈希表,然后在第二层利用哈希表的特性算出斜率,函数处理后作为地址进行插入,遇上冲突就判断两者key是否相同,相同则返回false,否则判断下一个cell直到empty。如果各点均匀分布的话复杂度也应该在O(n^2)

      你觉得这样做有问题嘛?

      • 你的hash表如何设计,需要多大空间?这是个问题;

        hash表和二叉树的结合,一种简单的思路就是对hash值冲突的元素建树,这样最坏情况就是所有的元素的hash值都冲突(出现这样的结果,hash函数简直是糟糕透了[偷笑])

  • 陈厚铭   2016/05/11

    先枚举一个点

    之后把它和其他的点的斜率一个一个插入到一个平衡二叉搜索树中,若插入失败则说明存在三点共线

    之后清空平衡二叉搜索树,枚举下一个点

  • 龙雀 野生程序员 2016/05/13

    储存(k,a)的时候用hash结合二叉树。就是hash之前每个簇中应该是链表,将其改为bst。如果碰撞也是局部碰撞,log(k),k小于n。

  • 陈厚铭   2016/05/15

    sorry,没审题,十分抱歉。

    我想了想觉得可以用离散化加哈希表来改进一下

    先用O(n^2)的时间求出任意两点所形成的线段对坐标轴产生的投影的距离的最小值。(其实就是min(x1-x2,y1-y2))

    然后以这个最小值为基础建立离散的坐标网格,并把这n个点一一映射到网格中去,使得每一个网格要么只包含一个点,要么不包含点。

    然后再用刚才的办法,只不过把平衡二叉搜索树换成哈希表

    先枚举一个网格,然后把它和其他网格的斜率算出来存入哈希表,要是有重复说明有三点共线的可能(因为这只是离散网格),就可以记录下来这两个网格的坐标,随后枚举下一个点。这样时间复杂度是O(n^2)。

    至于哈希表的设计,可以用建立一个bool类型的二维数组h[][],其中h[i][j]表示斜率为i/j。

    把所有记录过有“三点共线的可能”的点,还原到连续的空间下,再判断一下是否真的是三点共线。不出意外的话这步需要不了多少时间。

    时间复杂度为O(n^2),但有个缺点就是某些情况下空间开销有点太大。

  • Bricks_Porter   2016/05/15

    求出所有两点之间的斜率(n^2),然后排序(logn),如果斜率相同,可以按照点的x,y值比大小。然后可以在O(n^2)的时间内找到是否有斜率相同的对存在共同的点。

  • DocxsYang   2016/05/16

    就是求一条直线能穿过多少集合中多少个点,如果点数大于等于3,就说明有三点共享,类似可以看看这道题。

    http://blog.csdn.net/ljiabin/article/details/38904757

    我用代码写了下:

    Definition for a point.

  • DocxsYang   2016/05/16

     

    • lrscy 学生 2016/12/02

      如果还成最简分数存储的话效果会更好~毕竟float有精度误差~而且斜率不存在时候不好表示

  • 晴天 一枚小媛 2016/05/16

    图论加几何?

  • aaa   2016/07/19

    我目前只能想出解决办法,复杂度,回头考虑考虑,用有向图最小路径寻径,不存在三点最短路径等于两点的路径即可,两点间路径用勾股定理算