Divide Plane - 1point3acres

平分平面上的点
平面有一堆的点point(x, y), 选出其中的两个点，这两个点连成的线，可以把坐标系里的点分成两半，两边的点的个数相同。这位大哥的口音太重了，我跟他交流的过程中完全听不太懂。先提出了暴力解法，最后再提示下想到了优化的方法：找出bottom left most point, 固定这个点选出的线，肯定能平分两半。

用户visa 提到：

To determine which side of the line from A=(x1,y1) to B=(x2,y2) a point P=(x,y) falls on you need to compute the value:
d=(x−x1)(y2−y1)−(y−y1)(x2−x1)
If d<0 then the point lies on one side of the line, and if d>0 then it lies on the other side. If d=0 then the point lies exactly line.

To see whether points on the left side of the line are those with positive or negative values compute the value for d for a point you know is to the left of the line, such as (x1−1,y1) and then compare the sign with the point you are interested in.

https://www.1point3acres.com/bbs ... read&tid=491317

这题首先你得知道没有三点共线

然后就可以证明总存在任意两个点可以划分剩下所有的点

所以直接从一个点出发算跟每一个点的斜率, 排序即可

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=491317

我没写完，面试官说这个helper function可以不用写，估计是嫌我太慢了吧

To determine which side of the line from A=(x1,y1) to B=(x2,y2) a point P=(x,y) falls on you need to compute the value:- d=(x−x1)(y2−y1)−(y−y1)(x2−x1) If d<0 then the point lies on one side of the line, and if d>0 then it lies on the other side. If d=0 then the point lies exactly line. To see whether points on the left side of the line are those with positive or negative values compute the value for d for a point you know is to the left of the line, such as (x1−1,y1) and then compare the sign with the point you are interested in.

楼主，按照定理来说，他给的这个离散点矩阵，其中任意一个点，在这个矩阵中都能找到一个点，把这个矩阵一分为二，对于每一个新的点，按照我刚post上去的数学公式判断是否在上边或者下边，就可以了，这样时间复杂度就是O(N^2）

这一题我后来仔细写了一下，终于理解了烙印给的提示， 最下面最左边的点，可以保证其余点在这个点的一侧，然后对其余所有点按照斜率排序，如果斜率<0， 则 加上一个非常大的数，然后取中值，则一定满足条件。 完全不用写判断在哪侧的函数...

附上代码和测试用例。 测试用例我随即了1000次，每次随即100个点， 用leetcode maxpoint on one line的方法保证没有三个点在同一直线。测试用例全过。

我取了最下面最左边的点作为start point，保证了其余所有点在上半侧，然后将其余点按照斜率排序（注意负数加上一个很大的数保证），然后去中点。为了测试，我加上了判断哪侧的函数，实际这个函数用不到。

补充内容 (2019-3-7 14:55):

如果按照烙印的说法最左边最下面的点，那么斜率是负数似乎也不用加一个很大的值，直接按照斜率排序就好。

总的来说，这题刚出来很容易被这个"判断哪侧"搞慌...但是换个思路就柳暗花明了。

def split_points(points):

    # 去最左边最下面的点

    st = [1 << 32, 1 << 32]

    st_idx = None

    for i, (px, py) in enumerate(points):

        if px < st[0] or px == st[0] and py < st[1]:

            st = px, py

            st_idx = i

    points.pop(st_idx)

    INF = 1 << 31

    def cmp(p):

        k = (p[1] - st[1]) * 1.0 / (p[0] - st[0]) if p[0] != st[0] else INF

        return k

    # 按照斜率排序

    points = sorted(points, key=cmp)

    mid = points[len(points) / 2]

     

    return st, mid