Python：每日一题 377
本帖最后由 zltzlt 于 2020-4-16 12:53 编辑今天的题目：
在一个二维的花园中，有一些用 (x, y) 坐标表示的树。
由于安装费用十分昂贵，所以要先用最短的绳子围起所有的树。
只有当所有的树都被绳子包围时，花园才能围好栅栏。找到正好位于栅栏边界上的树的坐标。
说明：
1. 输入的点没有顺序，输出的点也没有顺序要求。
2. 所有的树应当被围在一起，不能剪断绳子来包围树或者把树分成一组以上。
3. 花园至少有一棵树。
4. 所有树的坐标都是不同的。
示例 1：
输入：[, , , , , ]
输出：[, , , , ]
解释：
示例 2：
输入：[, , ]
输出：[, , ]
解释：
即使树都在一条直线上，也需要先用绳子包围它们。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 March2615 于 2020-4-16 15:59 编辑
# 解题思路：
# 从最左边一棵树开始，逆时针绕着围
# 如果是逆时针转，则向量叉乘为正，否则，叉乘为负（可以想象成应该一直左转不能有右转）
# 叉乘要三个点，所以不足两个点的时候不管是不是为正，都要认为是边界上的
def daily377(trees: list) -> list:
if len(trees) < 4:# 小于四棵树的时候，肯定都在边界上了
return trees
def cross(p1, p2, p3):# p1->p2 & p2->p3
return (p1 - p2) * (p3 - p2) - (p1 - p2) * (p3 - p2)
down = []
for tree in sorted(trees):
while len(down) >= 2 and cross(down[-2], down[-1], tree) < 0:
down.pop()
down.append(tree)
up = []
for tree in sorted(trees, reverse=True):
while len(up) >= 2 and cross(up[-2], up[-1], tree) < 0:
up.pop()
up.append(tree)
result = []
for each in down[:-1] + up[:-1]:
if each not in result:
result.append(each)
return result
不知不觉一下午过去了{:10_285:} 本帖最后由 kinkon 于 2020-4-16 18:16 编辑
复杂度有点高，希望能过吧，看看能不能过，做这种题型还是比较吃力
def f377(arr):
n = len(arr)
if n < 4:
return arr
arr = sorted(arr, key = lambda x: (x, x))
temp = lambda o, x, y: (x - o) * (y - o) - (x - o) * (y - o)
left, right = [], []
for a in arr:
while len(left) > 1 and temp(left[-2], left[-1], a) < 0:
left.pop()
left.append(a)
for a in range(n -1, -1, -1):
while len(right) > 1 and temp(right[-2], right[-1], arr) < 0:
right.pop()
right.append(arr)
return left[:-1] + right[:-1] 直觉就是计算几何学中的求convex hull，贴个书上的伪代码，回头研究研究用python怎么实现
本帖最后由 TJBEST 于 2020-4-16 18:49 编辑
来看看我的史诗巨作，历时1个小时20分钟
def fun377(points):
def gcd(a,b):#计算最大公约数
while b:
a,b = b,a%b
return a
def getLine(point1,point2):#计算直线方程
if point1 == point2:
return (1,0,-point1)
elif point1 == point2:
return (0,1,-point1)
else:
a = point2 - point1
b = point1 - point2
c = point2*point1 - point1*point2
if a < 0:
a,b,c = -a,-b,-c
if c == 0:
T_ab = gcd(a,abs(b))
return (a//T_ab,b//T_ab,0)
else:
T_ab = gcd(a,abs(b))
T_ac = gcd(a,abs(c))
T_abc = gcd(T_ab,T_ac)
return (a//T_abc,b//T_abc,c//T_abc)
def getH(Line,point):#计算高（不按实际，仅正负号判断是否一侧）
return Line*point+Line*point+Line
if len(points) < 4:
return points
totalSet = set(tuple(each) for each in points )#元组多好，不要用序列，不hash
unKnown = totalSet.copy()#未知点集合
onBorder = set()#边界点集合
inBorder = set()#边界内部点集合
LineSet = set()#直线集合 形式 ax+by+c (a,b,c)
while unKnown:
tempPoint = unKnown.pop()
if (tempPoint in onBorder) or (tempPoint in inBorder):
pass
else:
tempSet = totalSet - (inBorder | {tempPoint})
while tempSet:
innerPoint = tempSet.pop()
tempLine = getLine(tempPoint,innerPoint)
if tempLine in LineSet:
continue
LineSet.add(tempLine)
#计算是否一侧？
H = [(getH(tempLine,each),each) for each in totalSet]#记录高和点
MaxH = max(H)
MinH = min(H)
if MaxH*MinH >= 0:#在一侧即边界
onBorder |= set( for each in H if each == 0])
break#该点是边界点 就不用测了
else:#最麻烦 去掉两端 都是in 两端无法判断
pointOnLine = for each in H if each == 0]
if pointOnLine != pointOnLine:
pointOnLine.sort(key = lambda each:each)
else:
pointOnLine.sort(key = lambda each:each)
inBorder |= set(pointOnLine)
if tempPoint in inBorder:
break
else:
tempSet = totalSet - (inBorder | {tempPoint,innerPoint})#得去掉 innerPoint避免死循环
else:
inBorder.add(tempPoint)
result = []
for each in onBorder:
result.append(list(each))
return result @zltzlt所有坐标都是整数吧？否则可能需要软判决。 本帖最后由 kinkon 于 2020-4-16 18:23 编辑
优化一下
def f377(arr):
n = len(arr)
if n < 4:
return arr
arr = sorted(arr, key = lambda x: (x, x))
temp = lambda o, x, y: (x - o) * (y - o) - (x - o) * (y - o)
left, right = [], []
for a in range(n):
while len(left) > 1 and temp(left[-2], left[-1], arr) < 0:
left.pop()
left.append(arr)
while len(right) > 1 and temp(right[-2], right[-1], arr[~a]) < 0:
right.pop()
right.append(arr[~a])
return left[:-1] + right[:-1] kinkon 发表于 2020-4-16 15:21
@zltzlt 有没有重复坐标？
4.所有树的坐标都是不同的 March2615 发表于 2020-4-16 15:50
4.所有树的坐标都是不同的
我觉得坐标都是整数吧，否则点在不在边界上 会出现问题。{:5_109:} 本帖最后由 kinkon 于 2020-4-16 18:25 编辑
@zltzlt 输出排序有要求吗？ TJBEST 发表于 2020-4-16 15:53
我觉得坐标都是整数吧，否则点在不在边界上 会出现问题。
按照我自己的解题思路是不用考虑是不是整数的
回复不能传图片好像
我把第一个测试用例的改成是没问题的
也可能是我哪没想到吧 March2615 发表于 2020-4-16 16:02
按照我自己的解题思路是不用考虑是不是整数的
回复不能传图片好像
我把第一个测试用例的改成
小数在编程语言中是存在问题的，需要软判决。因为如果你在过程中出现比大小 即> = <时是需要指定判决精度的 比如 某种精度下 3.1111和3.1110认为相等 @zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数 TJBEST 发表于 2020-4-16 16:09
小数在编程语言中是存在问题的，需要软判决。因为如果你在过程中出现比大小 即> =
这我倒是没考虑到
不过这样测试用例也太难找了
受教了，下次注意 TJBEST 发表于 2020-4-16 16:13
@zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数
这种题型应该不会出现有浮点数吧，我也是按整数来做的 kinkon 发表于 2020-4-16 16:31
这种题型应该不会出现有浮点数吧，我也是按整数来做的
不会 TJBEST 发表于 2020-4-16 16:13
@zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数
是整数 kinkon 发表于 2020-4-16 15:57
@zltzlt 输出排序有要求吗？
说明：
1. 输入的点没有顺序，输出的点也没有顺序要求。 def func377(arr):
def distance( p,q):
return (p-q) * (p-q) + (p-q) * (p- q)
def bottom(arr):
bottoms = arr
for i in arr:
if i<bottoms:
bottoms = i
return bottoms
def cross(p1, p2, p3):# p1->p2 & p2->p3
return (p1 - p2) * (p3 - p2) - (p1 - p2) * (p3 - p2)
def jiaodu(a,b):
c = (b-a)/(pow((b-a),2)+pow(b-a,2))
return c
n = len(arr)
if n < 3: return arr
stack = []
temp = arr[:]
bottoms = bottom(arr)
temp.remove(bottoms)
sorted(temp, key = lambda a: (jiaodu(bottoms,a),distance(bottoms,a)))
temp.insert(0,bottoms)
for i in range(1,n-1):
b = cross(temp,temp,temp)
if b<0:
stack.append(temp)
temp=temp
for each in stack:
arr.remove(each)
return arr kinkon 发表于 2020-4-16 12:40
复杂度有点高，希望能过吧，看看能不能过，做这种题型还是比较吃力
18 ms
页:
[1]
2