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

风魔孤行者

1. def f(list1):
   
2.     def x(list1):
   
3.         return list1[0]
   
4.     def y(list1):
   
5.         return list1[1]
   
6.     list2 = []
   
7.     list1 = sorted(list1,key=x)
   
8.     xmin = list1[0][0]
   
9.     xmin_list = []
   
10.     xmax = list1[-1][0]
    
11.     xmax_list = []
    
12.     for each in list1:
    
13.         if each[0] == xmin:
    
14.             list2.append(each)
    
15.             xmin_list.append(each[1])
    
16.         elif each[0] == xmax:
    
17.             list2.append(each)
    
18.             xmax_list.append(each[1])
    
19.    
    
20.     list1 = sorted(list1,key=y)
    
21.     ymin = list1[0][1]
    
22.     ymin_list = []
    
23.     ymax = list1[-1][1]
    
24.     ymax_list = []
    
25.     for each in list1:
    
26.         if each[1] == ymin:
    
27.             list2.append(each)
    
28.             ymin_list.append(each[0])
    
29.         elif each[1] == ymax:
    
30.             list2.append(each)
    
31.             ymax_list.append(each[0])
    
32. 
    
33.     xmin_list.sort()
    
34.     xmax_list.sort()
    
35.     ymin_list.sort()
    
36.     ymax_list.sort()
    
37. 
    
38.     def f1(p1,p2,p3):
    
39.         if abs((p2[1]-p1[1])/(p2[0]-p1[0]))<abs((p3[1]-p1[1])/(p3[0]-p1[0])):
    
40.             return 2
    
41.         elif abs((p2[1]-p1[1])/(p2[0]-p1[0]))==abs((p3[1]-p1[1])/(p3[0]-p1[0])):
    
42.             return 1
    
43.         else:
    
44.             return 0
    
45.         
    
46.     leftup,leftdown,rightup,rightdown = list1[:],list1[:],list1[:],list1[:]
    
47.     p1,p2,p3,p4,p5,p6,p7,p8 = [xmin,xmin_list[-1]],[ymax_list[0],ymax],[ymax_list[-1],ymax],[xmax,xmax_list[-1]],[xmax,xmax_list[0]],[ymin_list[-1],ymin],[ymin_list[0],ymin],[xmin,xmin_list[0]]
    
48.     h1,h2,h3,h4 = [],[],[],[]
    
49.     while leftup != []:
    
50.         for each in leftup.copy():
    
51.             if each[0]>=p2[0] or each[1]<=p1[1]:
    
52.                 leftup.remove(each)
    
53.             else:
    
54.                 if f1(p1,p2,each)==2:
    
55.                     h1 = []
    
56.                     h1.append(each)
    
57.                     p2 = each
    
58.                 elif f1(p1,p2,each)==1:
    
59.                     h1.append(each)
    
60.         if h1 != []:
    
61.             list2 += h1
    
62.             h1 = sorted(h1,key=y)
    
63.             p1 = h1[-1]
    
64.             p2 = [ymax_list[0],ymax]
    
65.             for m in h1:
    
66.                 leftup.remove(m)
    
67.         else:
    
68.             break
    
69.     while rightup != []:
    
70.         for each in rightup.copy():
    
71.             if each[0]<=p3[0] or each[1]<=p4[1]:
    
72.                 rightup.remove(each)
    
73.             else:
    
74.                 if f1(p4,p3,each)==2:
    
75.                     h2 = []
    
76.                     h2.append(each)
    
77.                     p3 = each
    
78.                 elif f1(p4,p3,each)==1:
    
79.                     h2.append(each)
    
80.         if h2 != []:
    
81.             list2 += h2
    
82.             h2 = sorted(h2,key=y)
    
83.             p4 = h2[-1]
    
84.             p3 = [ymax_list[-1],ymax]
    
85.             for m in h2:
    
86.                 rightup.remove(m)
    
87.         else:
    
88.             break
    
89.     while leftdown != []:
    
90.         for each in leftdown.copy():
    
91.             if each[0]>=p7[0] or each[1]>=p8[1]:
    
92.                 leftdown.remove(each)
    
93.             else:
    
94.                 if f1(p8,p7,each)==2:
    
95.                     h4 = []
    
96.                     h4.append(each)
    
97.                     p7 = each
    
98.                 elif f1(p8,p7,each)==1:
    
99.                     h4.append(each)
    
100.         if h4 != []:
     
101.             list2 += h4
     
102.             h4 = sorted(h4,key=x)
     
103.             p8 = h4[-1]
     
104.             p7 = [ymin_list[0],ymin]
     
105.             for m in h4:
     
106.                 leftdown.remove(m)
     
107.         else:
     
108.             break
     
109.     while rightdown != []:
     
110.         for each in rightdown.copy():
     
111.             if each[0]<=p6[0] or each[1]>=p5[1]:
     
112.                 rightdown.remove(each)
     
113.             else:
     
114.                 if f1(p5,p6,each)==2:
     
115.                     h3 = []
     
116.                     h3.append(each)
     
117.                     p6 = each
     
118.                 elif f1(p5,p6,each)==1:
     
119.                     h3.append(each)
     
120.         if h3 != []:
     
121.             list2 += h3
     
122.             h3 = sorted(h3,key=x)
     
123.             p5 = h3[0]
     
124.             p6 = [ymin_list[-1],ymin]
     
125.             for m in h3:
     
126.                 rightdown.remove(m)
     
127.         else:
     
128.             break
     
129.     return list2

复制代码