[已解决]Python：每日一题 377

zltzlt

今天的题目：

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。

由于安装费用十分昂贵，所以要先用最短的绳子围起所有的树。

只有当所有的树都被绳子包围时，花园才能围好栅栏。找到正好位于栅栏边界上的树的坐标。

说明：
1. 输入的点没有顺序，输出的点也没有顺序要求。
2. 所有的树应当被围在一起，不能剪断绳子来包围树或者把树分成一组以上。
3. 花园至少有一棵树。
4. 所有树的坐标都是不同的。

示例 1：

输入：[[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]
输出：[[1, 1], [2, 0], [4, 2], [2, 4], [3, 3]]
解释：

示例 2：

输入：[[1, 2], [2, 2], [4, 2]]
输出：[[1, 2], [2, 2], [4, 2]]
解释：

即使树都在一条直线上，也需要先用绳子包围它们。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

March2615

2020-4-16 12:09:06

1. # 解题思路：
   
2. # 从最左边一棵树开始，逆时针绕着围
   
3. # 如果是逆时针转，则向量叉乘为正，否则，叉乘为负（可以想象成应该一直左转不能有右转）
   
4. # 叉乘要三个点，所以不足两个点的时候不管是不是为正，都要认为是边界上的
   
5. def daily377(trees: list) -> list:
   
6.     if len(trees) < 4:  # 小于四棵树的时候，肯定都在边界上了
   
7.         return trees
   
8. 
   
9.     def cross(p1, p2, p3):  # p1->p2 & p2->p3
   
10.         return (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0])
    
11. 
    
12.     down = []
    
13.     for tree in sorted(trees):
    
14.         while len(down) >= 2 and cross(down[-2], down[-1], tree) < 0:
    
15.             down.pop()
    
16.         down.append(tree)
    
17. 
    
18.     up = []
    
19.     for tree in sorted(trees, reverse=True):
    
20.         while len(up) >= 2 and cross(up[-2], up[-1], tree) < 0:
    
21.             up.pop()
    
22.         up.append(tree)
    
23. 
    
24.     result = []
    
25.     for each in down[:-1] + up[:-1]:
    
26.         if each not in result:
    
27.             result.append(each)
    
28.     return result

复制代码

不知不觉一下午过去了

跳转到最佳答案楼层

March2615

1. # 解题思路：
   
2. # 从最左边一棵树开始，逆时针绕着围
   
3. # 如果是逆时针转，则向量叉乘为正，否则，叉乘为负（可以想象成应该一直左转不能有右转）
   
4. # 叉乘要三个点，所以不足两个点的时候不管是不是为正，都要认为是边界上的
   
5. def daily377(trees: list) -> list:
   
6.     if len(trees) < 4:  # 小于四棵树的时候，肯定都在边界上了
   
7.         return trees
   
8. 
   
9.     def cross(p1, p2, p3):  # p1->p2 & p2->p3
   
10.         return (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0])
    
11. 
    
12.     down = []
    
13.     for tree in sorted(trees):
    
14.         while len(down) >= 2 and cross(down[-2], down[-1], tree) < 0:
    
15.             down.pop()
    
16.         down.append(tree)
    
17. 
    
18.     up = []
    
19.     for tree in sorted(trees, reverse=True):
    
20.         while len(up) >= 2 and cross(up[-2], up[-1], tree) < 0:
    
21.             up.pop()
    
22.         up.append(tree)
    
23. 
    
24.     result = []
    
25.     for each in down[:-1] + up[:-1]:
    
26.         if each not in result:
    
27.             result.append(each)
    
28.     return result

复制代码

不知不觉一下午过去了

kinkon

复杂度有点高，希望能过吧，看看能不能过，做这种题型还是比较吃力

1. def f377(arr):
   
2.     n = len(arr)
   
3.     if n < 4:
   
4.         return arr
   
5.     arr = sorted(arr, key = lambda x: (x[0], x[1]))
   
6.     temp = lambda o, x, y: (x[0] - o[0]) * (y[1] - o[1]) - (x[1] - o[1]) * (y[0] - o[0])
   
7.     left, right = [], []
   
8.     for a in arr:
   
9.         while len(left) > 1 and temp(left[-2], left[-1], a) < 0:
   
10.             left.pop()
    
11.         left.append(a)
    
12.         
    
13.     for a in range(n -1, -1, -1):
    
14.         while len(right) > 1 and temp(right[-2], right[-1], arr[a]) < 0:
    
15.             right.pop()
    
16.         right.append(arr[a])
    
17.     return left[:-1] + right[:-1]

复制代码

skittles5

直觉就是计算几何学中的求convex hull，贴个书上的伪代码，回头研究研究用python怎么实现

TJBEST

来看看我的史诗巨作，历时1个小时20分钟

1. def fun377(points):
   
2.     def gcd(a,b):#计算最大公约数
   
3.         while b:
   
4.             a,b = b,a%b
   
5.         return a
   
6.     def getLine(point1,point2):#计算直线方程
   
7.         if point1[0] == point2[0]:
   
8.             return (1,0,-point1[0])
   
9.         elif point1[1] == point2[1]:
   
10.             return (0,1,-point1[1])
    
11.         else:
    
12.             a = point2[1] - point1[1]
    
13.             b = point1[0] - point2[0]
    
14.             c = point2[0]*point1[1] - point1[0]*point2[1]
    
15.             if a < 0:
    
16.                 a,b,c = -a,-b,-c
    
17.             if c == 0:
    
18.                 T_ab = gcd(a,abs(b))
    
19.                 return (a//T_ab,b//T_ab,0)
    
20.             else:
    
21.                 T_ab = gcd(a,abs(b))
    
22.                 T_ac = gcd(a,abs(c))
    
23.                 T_abc = gcd(T_ab,T_ac)
    
24.                 return (a//T_abc,b//T_abc,c//T_abc)
    
25.     def getH(Line,point):#计算高（不按实际，仅正负号判断是否一侧）
    
26.         return Line[0]*point[0]+Line[1]*point[1]+Line[2]
    
27. 
    
28.     if len(points) < 4:
    
29.         return points
    
30.   
    
31.     totalSet = set(tuple(each) for each in points )#元组多好，不要用序列，不hash
    
32.     unKnown = totalSet.copy()#未知点集合
    
33.     onBorder = set()#边界点集合
    
34.     inBorder = set()#边界内部点集合
    
35.     LineSet = set()#直线集合 形式 ax+by+c (a,b,c)
    
36.     while unKnown:
    
37.         tempPoint = unKnown.pop()
    
38.         if (tempPoint in onBorder) or (tempPoint in inBorder):
    
39.             pass
    
40.         else:
    
41.             tempSet = totalSet - (inBorder | {tempPoint})
    
42.             while tempSet:
    
43.                 innerPoint = tempSet.pop()
    
44.                 tempLine = getLine(tempPoint,innerPoint)
    
45.                 if tempLine in LineSet:
    
46.                     continue
    
47.                 LineSet.add(tempLine)
    
48.                 #计算是否一侧？
    
49.                 H = [(getH(tempLine,each),each) for each in totalSet]#记录高和点
    
50.                 MaxH = max(H)[0]
    
51.                 MinH = min(H)[0]
    
52.                 if MaxH*MinH >= 0:#在一侧即边界
    
53.                     onBorder |= set([each[1] for each in H if each[0] == 0])
    
54.                     break#该点是边界点 就不用测了
    
55.                 else:#最麻烦 去掉两端 都是in 两端无法判断
    
56.                     pointOnLine = [each[1] for each in H if each[0] == 0]
    
57.                     if pointOnLine[0][0] != pointOnLine[1][0]:
    
58.                          pointOnLine.sort(key = lambda each:each[0])
    
59.                     else:
    
60.                          pointOnLine.sort(key = lambda each:each[1])
    
61.                     inBorder |= set(pointOnLine[1:-1])
    
62.                     if tempPoint in inBorder:
    
63.                         break
    
64.                     else:
    
65.                         tempSet = totalSet - (inBorder | {tempPoint,innerPoint})#得去掉 innerPoint避免死循环
    
66.             else:
    
67.                 inBorder.add(tempPoint)
    
68.     result = []
    
69.     for each in onBorder:
    
70.         result.append(list(each))
    
71.     return result

复制代码

TJBEST

@zltzlt  所有坐标都是整数吧？否则可能需要软判决。

kinkon

优化一下

1. def f377(arr):
   
2.     n = len(arr)
   
3.     if n < 4:
   
4.         return arr
   
5.     arr = sorted(arr, key = lambda x: (x[0], x[1]))
   
6.     temp = lambda o, x, y: (x[0] - o[0]) * (y[1] - o[1]) - (x[1] - o[1]) * (y[0] - o[0])         
   
7.     left, right = [], []
   
8.     for a in range(n):
   
9.         
   
10.         while len(left) > 1 and temp(left[-2], left[-1], arr[a]) < 0:
    
11.             left.pop()
    
12.         left.append(arr[a])
    
13.         
    
14.         while len(right) > 1 and temp(right[-2], right[-1], arr[~a]) < 0:
    
15.             right.pop()
    
16.         right.append(arr[~a])
    
17.         
    
18.     return left[:-1] + right[:-1]

复制代码

March2615

kinkon 发表于 2020-4-16 15:21
@zltzlt 有没有重复坐标？

4.所有树的坐标都是不同的

TJBEST

March2615 发表于 2020-4-16 15:50
4.所有树的坐标都是不同的

我觉得坐标都是整数吧，否则点在不在边界上 会出现问题。

kinkon

@zltzlt 输出排序有要求吗？

March2615

TJBEST 发表于 2020-4-16 15:53
我觉得坐标都是整数吧，否则点在不在边界上 会出现问题。

按照我自己的解题思路是不用考虑是不是整数的
回复不能传图片好像
我把第一个测试用例的[3,3]改成[3.5,3.5]是没问题的
也可能是我哪没想到吧

TJBEST

March2615 发表于 2020-4-16 16:02
按照我自己的解题思路是不用考虑是不是整数的
回复不能传图片好像
我把第一个测试用例的[3,3]改成[3.5, ...

小数在编程语言中是存在问题的，需要软判决。因为如果你在过程中出现比大小 即> = <时是需要指定判决精度的 比如 某种精度下 3.1111和3.1110认为相等

TJBEST

@zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数

March2615

TJBEST 发表于 2020-4-16 16:09
小数在编程语言中是存在问题的，需要软判决。因为如果你在过程中出现比大小 即> =

这我倒是没考虑到
不过这样测试用例也太难找了

受教了，下次注意

kinkon

TJBEST 发表于 2020-4-16 16:13
@zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数

这种题型应该不会出现有浮点数吧，我也是按整数来做的

zltzlt

kinkon 发表于 2020-4-16 16:31
这种题型应该不会出现有浮点数吧，我也是按整数来做的

不会

zltzlt

TJBEST 发表于 2020-4-16 16:13
@zltzlt 我先按全是整数来做吧，否则软判决太麻烦，需要精度控制，题目中没说，我觉得应该是坐标整数

是整数

zltzlt

kinkon 发表于 2020-4-16 15:57
@zltzlt 输出排序有要求吗？

说明：
1. 输入的点没有顺序，输出的点也没有顺序要求。

whosyourdaddy

def func377(arr):
    def distance( p,  q):
        return (p[0]-q[0]) * (p[0]-q[0]) + (p[1]-q[1]) * (p[1]- q[1])

    def bottom(arr):
        bottoms = arr[0]
        for i in arr:
            if i[1]<bottoms[1]:
                bottoms = i
        return bottoms
    def cross(p1, p2, p3):  # p1->p2 & p2->p3
        return (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0])
    def jiaodu(a,b):
        c = (b[0]-a[0])/(pow((b[1]-a[1]),2)+pow(b[0]-a[0],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[i-1],temp[i],temp[i+1])
        if b<0:
            stack.append(temp[i])
            temp[i]=temp[i-1]
    for each in stack:
        arr.remove(each)
    return arr

zltzlt

kinkon 发表于 2020-4-16 12:40
复杂度有点高，希望能过吧，看看能不能过，做这种题型还是比较吃力

18 ms