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

阴阳神万物主

难度评级：普通
要素分析：数论
随机输入生成器，送给有需要的人：如果觉得好用，麻烦评个分呗

1. from random import randint as r
   
2. def gent(x=[0,4],y=[0,4],m=8,n=5,f=False):
   
3.     '''
   
4.     参数说明：
   
5.         x:'横轴取值闭区间'默认为[0,4]
   
6.         y:'纵轴取值闭区间'默认为[0,4]
   
7.         m:'最多允许多少棵树'默认为8
   
8.         n:'生成数量'默认生成5个测试数据
   
9.         f:'是否固定树的颗数'默认为随机颗树
   
10.     '''
    
11.     x1,x2 = x
    
12.     y1,y2 = y
    
13.     size = min((x2-x1+1)*(y2-y1+1),m)
    
14.     for i in range(n):
    
15.         lst = []
    
16.         for j in range(size if f else r(1,size)):
    
17.             while 1:
    
18.                 pos = [r(x1,x2),r(y1,y2)]
    
19.                 if pos not in lst:
    
20.                     lst.append(pos)
    
21.                     break
    
22.         yield lst
    

复制代码

解题代码1：

1. def solve(trees:'list og points by list')->list:
   
2.     class Func:
   
3.         '''
   
4.         y = kx + b
   
5.         k = (y1-y2)/(x1-x2)
   
6.         b = y - kx
   
7.         '''
   
8.         def __init__(self,p1,p2):
   
9.             x1,y1 = p1
   
10.             x2,y2 = p2
    
11.             self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
    
12.             self.b = y1 - self.k*x1 if self.k!=None else x1
    
13.         def cmp(self,pos):
    
14.             x,y = pos
    
15.             if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
    
16.             ny = self.k*x + self.b
    
17.             return 0 if y==ny else 1 if y > ny else -1
    
18.     res = []
    
19.     l = len(trees)
    
20.     if l <= 3:return trees
    
21.     for a in range(l-1):
    
22.         for b in range(a+1,l):
    
23.             f =  Func(trees[a],trees[b])
    
24.             c = [f.cmp(pos) for pos in trees]
    
25.             if not(1 in c and -1 in c):
    
26.                 while 0 in c:
    
27.                     n = c.index(0)
    
28.                     if trees[n] not in res:res.append(trees[n])
    
29.                     c[n] += 1
    
30.     return res
    
31. 
    
32. if __name__ == '__main__':
    
33.     print('示例1 输出：',solve([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]))
    
34.     print('示例2 输出：',solve([[1, 2], [2, 2], [4, 2]]))
    

复制代码

思路解说：
整体就是一个简单的线性规划问题，所有点两两相连，若所有点都在线的同一侧或者就在线上，那么这条线就是边界。
当然，我上面这个属于是暴力规划，还有更加巧妙的，就是下面那个。

解题代码2：

1. class Func:
   
2.     '''
   
3.     y = kx + b
   
4.     k = (y1-y2)/(x1-x2)
   
5.     b = y - kx
   
6.     '''
   
7.     def __init__(self,p1,p2):
   
8.         x1,y1 = p1
   
9.         x2,y2 = p2
   
10.         self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
    
11.         self.b = y1 - self.k*x1 if self.k!=None else x1
    
12.     def cmp(self,pos):
    
13.         x,y = pos
    
14.         if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
    
15.         ny = round(self.k*x + self.b,1)
    
16.         return 0 if y==ny else 1 if y > ny else -1
    
17.    
    
18. def solve(trees:'list og points by list')->list:
    
19.     res = []
    
20.     l = len(trees)
    
21.     if l <= 3:return trees
    
22.     trees.sort()
    
23.     a,b = 0,0
    
24.     plan = [0]*l#标记非端边界点
    
25.     flg = 1
    
26.     while flg:
    
27.         b = (b+1)%l
    
28.         if plan[b]:continue
    
29.         if b == a:a = (a+1)%l;b=a
    
30.         f =  Func(trees[a],trees[b])#解析直线函数
    
31.         c = [f.cmp(pos) for pos in trees]#检查所有点与直线的关系
    
32.         if not(1 in c and -1 in c):#所有点均在直线的同一侧，或者在直线上
    
33.             online = []
    
34.             while 0 in c:
    
35.                 n = c.index(0)
    
36.                 online.append(trees[n])
    
37.                 if trees[n] not in res:res.append(trees[n])#将边界点加入输出列表
    
38.                 elif not plan[n]:flg = 0
    
39.                 c[n] += 1
    
40.                 if n!=a:plan[n] = 1
    
41.             online.sort()
    
42.             ia = online.index(trees[a])
    
43.             ib = online.index(trees[b])
    
44.             a = trees.index(online[-1 if ib>ia else 0])
    
45.             b = a#从线的一端直接到另一端，跳过中间的已被标记的点
    
46.     return res
    
47.         
    
48. if __name__ == '__main__':
    
49.     print('示例1 输出：',solve_1([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]))
    
50.     print('示例2 输出：',solve_1([[1, 2], [2, 2], [4, 2]]))
    
51.    

复制代码

我自己测试的用时是，在51*51的区域内，最多允许60颗树存在，100个随机测试用例
法一平均用时：36.3805ms
法二平均用时：6.2350ms
我自己测试用时的代码：

1. >>> import time
   
2. >>> def pt(b,x=5,y=5):        #在发现输出数据不同时，用平面图的方式呈现出数据，便于肉眼分辨
   
3.         plan = [[0]*y for i in range(x)]
   
4.         for i,j in b:
   
5.                 plan[i][j] = 1
   
6.         for line in plan:
   
7.                 print(line)
   
8. 
   
9. >>> if 1:
   
10.         t1,t2 = [],[]
    
11.         for each in gent([0,50],[0,50],m=60,n=100):
    
12.                 a = time.perf_counter()
    
13.                 s1 = solve_1(each)
    
14.                 b = time.perf_counter()
    
15.                 t1.append((b-a)*1000)
    
16.                 a = time.perf_counter()
    
17.                 s2 = solve_2(each)
    
18.                 b = time.perf_counter()
    
19.                 t2.append((b-a)*1000)
    
20.                 for each in s1:          #这个二层循环是检查两种方法的结果是否一致的，如不需要，可直接删去
    
21.                         if each not in s2:
    
22.                                 print('input',len(each))
    
23.                                 pt(each,51,51)
    
24.                                 print('s1',(s1))
    
25.                                 pt(s1,51,51)
    
26.                                 print('s2',(s2))
    
27.                                 pt(s2,51,51)
    
28.                                 break
    
29.         print('法一平均用时：%0.4fms\n法二平均用时：%0.4fms\n总共用时%0.4fms'%(sum(t1)/len(t1),sum(t2)/len(t2),sum(t1+t2)))

复制代码