活跃农民
- 积分
- 625
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-3-7
- 最后登录
- 1970-1-1
|
想请问一下为啥斜率是负的一定要加上一个大数(2*Inf)?感觉就把负的留在那儿直接排序也可以做?附上我的代码,也都跑过了你的test case
- def split(points):
- if not points or len(points) < 2 or len(points) % 2:
- return [],[]
-
- sx, sy = points[0]
- for i in xrange(1, len(points)):
- x, y = points[i]
- if x < sx:
- sx, sy = x, y
-
- slopes = []
- for x, y in points:
- if x == sx and y == sy:
- continue
- slopes.append((getSlope(sx, sy, x, y), x, y))
-
- slopes.sort()
- _, ex, ey = slopes[len(slopes) / 2]
-
- def count(st, end):
- num = 0
- sx, sy = st
- ex, ey = end
- for px, py in points:
- if (px, py) == (ex, ey) or (px, py) == (sx, sy) :
- continue
- if (ex - sx) * (py - sy) - (ey - sy) * (px - sx) < 0:
- num += 1
-
- return num
-
- assert count([sx, sy], [ex, ey]) == (len(points) - 2) / 2, (points, [sx, sy], [ex, ey])
-
-
- 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 |
|