平分平面上的点

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

好像这题我一年前给人mock过。。。楼上说的都不完美。事实上，只要保证不三点共线，可以以平面上任何一个点作为轴心建立一条直线，旋转这条直线必然有一个角度能将平面上所有的点分为数目相等的两份。
贡献一下我的C++的代码。

您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

如果有兴趣，可以关注一下我每日讲题的youtube：https://www.youtube.com/playlist ... sYCcDTXIMVaHSlsnLzL

步惊云 发表于 2019-3-8 08:14
这题首先你得知道没有三点共线

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

是的，按照斜率排序去中间值就好了。但是需要起点需要不能随便取，最好的起点是最左下角，因为这样斜率排序之后表现在图里就是按照逆时针排序

1. def split_points(points):
   
2.     #points = sorted(points, key=lambda x: x[1])
   
3.     st = [1 << 32, 1 << 32]
   
4.     st_idx = None
   
5.     for i, (px, py) in enumerate(points):
   
6.         if py < st[1] or py == st[1] and px < st[0]:
   
7.             st = px, py
   
8.             st_idx = i
   
9. 
   
10.     # 判断点在哪侧。实际不用，只是用来验证正确
    
11.     def count(st, end):
    
12.         num = 0
    
13.         sx, sy = st
    
14.         ex, ey = end
    
15.         for px, py in points:
    
16.             if (px, py) == (ex, ey):
    
17.                 continue
    
18.             if (ex - sx) * (py - sy) - (ey - sy) * (px - sx) < 0:
    
19.                 num += 1
    
20.         return num
    
21. 
    
22. 
    
23.     points.pop(st_idx)
    
24.     INF = 1 << 31
    
25.     def cmp(p):
    
26.         k = (p[1] - st[1]) * 1.0 / (p[0] - st[0]) if p[0] != st[0] else INF
    
27.         if k < 0:
    
28.             k += 2 * INF
    
29.         return k
    
30.     points = sorted(points, key=cmp)
    
31.     mid = points[len(points) / 2]
    
32.     assert count(st, mid) == len(points) / 2, (points, st, mid)
    

复制代码

补充内容 (2019-3-26 14:10):
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]:
     ...

不一定要最左下的点吧，我觉得最左或者最右或者最高或者最低的点当起点都可以

umialpha 发表于 2019-3-26 14:09
是的，按照斜率排序去中间值就好了。但是需要起点需要不能随便取，最好的起点是最左下角，因为这样斜率排 ...

想请问一下为啥斜率是负的一定要加上一个大数（2*Inf）?感觉就把负的留在那儿直接排序也可以做？附上我的代码，也都跑过了你的test case

1.     def split(points):
   
2.         if not points or len(points) < 2 or len(points) % 2:
   
3.             return [],[]
   
4.         
   
5.         sx, sy = points[0]
   
6.         for i in xrange(1, len(points)):
   
7.             x, y = points[i]
   
8.             if x < sx:
   
9.                 sx, sy = x, y
   
10.         
    
11.         slopes = []
    
12.         for x, y in points:
    
13.             if x == sx and y == sy:
    
14.                 continue
    
15.             slopes.append((getSlope(sx, sy, x, y), x, y))
    
16.         
    
17.         slopes.sort()
    
18.         _, ex, ey = slopes[len(slopes) / 2]
    
19.         
    
20.         def count(st, end):
    
21.             num = 0
    
22.             sx, sy = st
    
23.             ex, ey = end
    
24.             for px, py in points:
    
25.                 if (px, py) == (ex, ey) or (px, py) == (sx, sy) :
    
26.                     continue
    
27.                 if (ex - sx) * (py - sy) - (ey - sy) * (px - sx) < 0:
    
28.                     num += 1
    
29.         
    
30.             return num
    
31.         
    
32.         assert count([sx, sy], [ex, ey]) == (len(points) - 2) / 2, (points, [sx, sy], [ex, ey])
    
33.         
    
34.         
    
35.         return [sx, sy], [ex, ey]

复制代码

补充内容 (2019-4-12 07:50):
忘了附上我的getSlope函数。。。
    def getSlope(x0, y0, x, y):
        dy = y - y0
        dx = x - x0
        if dx == 0:
            if dy > 0:
                return float("Inf")
            els...

补充内容 (2019-4-12 07:50):
接上一个。。。
if dx == 0:
            if dy > 0:
                return float("Inf")
            else:
                return -float("Inf")
        return float(dy) / dx

有木有大佬讲一哈原理

我记得原来算法课讲过这一题