不知不觉一下午过去了
17 ms TJBEST 发表于 2020-4-16 14:58
来看看我的史诗巨作，历时1个小时20分钟
输入以下数据超时：
kinkon 发表于 2020-4-16 15:21
优化一下
15 ms whosyourdaddy 发表于 2020-4-16 20:11
def func377(arr):
def distance( p,q):
return (p-q) * (p-q) + (p-q) ...
解答错误
输入：[, , , , , , , ]
输出：[, , , , , ]
预期结果：[, , , , , ] import math
def f377(points):
n = len(points)
if n == 0:
return 0
if n <= 3:
return points
def get_bottom_point(points):
min_index = 0
n = len(points)
for i in range(0, n):
if points < points or (points == points and points < points):
min_index = i
return min_index
def f2(points, center_point):
n = len(points)
cos_value = []
rank = []
norm_list = []
for i in range(0, n):
point_ = points
point = -center_point, point_-center_point]
rank.append(i)
norm_value = math.sqrt(point*point + point*point)
norm_list.append(norm_value)
if norm_value == 0:
cos_value.append(1)
else:
cos_value.append(point / norm_value)
for i in range(0, n-1):
index = i + 1
while index > 0:
if cos_value > cos_value or (cos_value == cos_value and norm_list > norm_list):
temp = cos_value
temp_rank = rank
temp_norm = norm_list
cos_value = cos_value
rank = rank
norm_list = norm_list
cos_value = temp
rank = temp_rank
norm_list = temp_norm
index = index-1
else:
break
sorted_points = []
for i in rank:
sorted_points.append(points)
return sorted_points
def vector_angle(vector):
norm_ = math.sqrt(vector*vector + vector*vector)
if norm_ == 0:
return 0
angle = math.acos(vector/norm_)
if vector >= 0:
return angle
else:
return 2*math.pi - angle
def coss_multi(v1, v2):
return v1*v2 - v1*v2
bottom_index = get_bottom_point(points)
bottom_point = points.pop(bottom_index)
sorted_points = f2(points, bottom_point)
m = len(sorted_points)
if m <2 :
return points
stack = []
stack.append(bottom_point)
stack.append(sorted_points)
stack.append(sorted_points)
for i in range(2, m):
length = len(stack)
top = stack
next_top = stack
v1 = -next_top, sorted_points-next_top]
v2 = -next_top, top-next_top]
while coss_multi(v1, v2) > 0:
stack.pop()
length = len(stack)
top = stack
next_top = stack
v1 = - next_top, sorted_points - next_top]
v2 = - next_top, top - next_top]
stack.append(sorted_points)
return stack
print(f377([, , ]))
print(f377([, , , , , ])) 总想起个好名字 发表于 2020-4-16 22:23
？ 数学不好的人飘过...高等数学没有学过...怎么办 本帖最后由 TJBEST 于 2020-4-17 17:18 编辑
楼主帮忙测测吧 @zltzlt
def fun377(points):
if len(points) < 4:
return points
dealWith = sorted(points)
Left = dealWith
Right = dealWith[-1]
del dealWith
result =
previous = Left
while True:
if previous == Left:
comList = > previous) or (i > previous)]
elif previous == Right:
comList = == previous) and (i < previous)]
else:
comList = > previous]
comList.sort()
if comList == Left:
previous = comList
result.append(previous)
dealWith.remove(previous)
elif previous == Right:
previous = comList[-1]
result.append(previous)
dealWith.remove(previous)
else:
comList.sort(key = lambda ex:(((ex-previous)/(ex-previous)),-ex))
previous = comList.pop()
result.append(previous)
dealWith.remove(previous)
if previous == Right:
break
dealWith.append(Left)
while True:
if previous == Left:
comList = ==previous) and (i > previous)]
elif previous == Right:
comList = < previous) or (i < previous)]
else:
comList = < previous]
comList.sort()
if comList[-1] == Right:
previous = comList.pop()
result.append(previous)
dealWith.remove(previous)
elif previous == Left:
previous = comList
result.append(previous)
dealWith.remove(previous)
else:
comList.sort(key = lambda ex:(((ex-previous)/(ex-previous)),ex))
previous = comList.pop()
result.append(previous)
dealWith.remove(previous)
if previous == Left:
result.remove(Left)
break
return result 本帖最后由 kinkon 于 2020-4-17 11:37 编辑
自己想的一个测试用例：[, , , , , , , ,]
输出：[, , , , ] ouyunfu 发表于 2020-4-16 21:35
解答错误
输入：[, , , , , , , , , , , , , , , , , ]
输出：[, , , , , , , , , , , , , , , ]
预期结果：[, , , , , , , , , , , , , , , ] @zltzlt 楼主 新代码见28层 待我上机我来画的试试 TJBEST 发表于 2020-4-17 11:16
楼主帮忙测测吧 @zltzlt
56 ms 本帖最后由 阴阳神万物主 于 2020-4-18 05:36 编辑
难度评级：普通
要素分析：数论
随机输入生成器，送给有需要的人：如果觉得好用，麻烦评个分呗
from random import randint as r
def gent(x=,y=,m=8,n=5,f=False):
'''
参数说明：
x:'横轴取值闭区间'默认为
y:'纵轴取值闭区间'默认为
m:'最多允许多少棵树'默认为8
n:'生成数量'默认生成5个测试数据
f:'是否固定树的颗数'默认为随机颗树
'''
x1,x2 = x
y1,y2 = y
size = min((x2-x1+1)*(y2-y1+1),m)
for i in range(n):
lst = []
for j in range(size if f else r(1,size)):
while 1:
pos =
if pos not in lst:
lst.append(pos)
break
yield lst
解题代码1：
def solve(trees:'list og points by list')->list:
class Func:
'''
y = kx + b
k = (y1-y2)/(x1-x2)
b = y - kx
'''
def __init__(self,p1,p2):
x1,y1 = p1
x2,y2 = p2
self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
self.b = y1 - self.k*x1 if self.k!=None else x1
def cmp(self,pos):
x,y = pos
if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
ny = self.k*x + self.b
return 0 if y==ny else 1 if y > ny else -1
res = []
l = len(trees)
if l <= 3:return trees
for a in range(l-1):
for b in range(a+1,l):
f =Func(trees,trees)
c =
if not(1 in c and -1 in c):
while 0 in c:
n = c.index(0)
if trees not in res:res.append(trees)
c += 1
return res
if __name__ == '__main__':
print('示例1 输出：',solve([, , , , , ]))
print('示例2 输出：',solve([, , ]))
思路解说：
整体就是一个简单的线性规划问题，所有点两两相连，若所有点都在线的同一侧或者就在线上，那么这条线就是边界。
当然，我上面这个属于是暴力规划，还有更加巧妙的，就是下面那个。
解题代码2：
class Func:
'''
y = kx + b
k = (y1-y2)/(x1-x2)
b = y - kx
'''
def __init__(self,p1,p2):
x1,y1 = p1
x2,y2 = p2
self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
self.b = y1 - self.k*x1 if self.k!=None else x1
def cmp(self,pos):
x,y = pos
if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
ny = round(self.k*x + self.b,1)
return 0 if y==ny else 1 if y > ny else -1
def solve(trees:'list og points by list')->list:
res = []
l = len(trees)
if l <= 3:return trees
trees.sort()
a,b = 0,0
plan = *l#标记非端边界点
flg = 1
while flg:
b = (b+1)%l
if plan:continue
if b == a:a = (a+1)%l;b=a
f =Func(trees,trees)#解析直线函数
c = #检查所有点与直线的关系
if not(1 in c and -1 in c):#所有点均在直线的同一侧，或者在直线上
online = []
while 0 in c:
n = c.index(0)
online.append(trees)
if trees not in res:res.append(trees)#将边界点加入输出列表
elif not plan:flg = 0
c += 1
if n!=a:plan = 1
online.sort()
ia = online.index(trees)
ib = online.index(trees)
a = trees.index(online[-1 if ib>ia else 0])
b = a#从线的一端直接到另一端，跳过中间的已被标记的点
return res
if __name__ == '__main__':
print('示例1 输出：',solve_1([, , , , , ]))
print('示例2 输出：',solve_1([, , ]))
我自己测试的用时是，在51*51的区域内，最多允许60颗树存在，100个随机测试用例
法一平均用时：36.3805ms
法二平均用时：6.2350ms
我自己测试用时的代码：
>>> import time
>>> def pt(b,x=5,y=5): #在发现输出数据不同时，用平面图的方式呈现出数据，便于肉眼分辨
plan = [*y for i in range(x)]
for i,j in b:
plan = 1
for line in plan:
print(line)
>>> if 1:
t1,t2 = [],[]
for each in gent(,,m=60,n=100):
a = time.perf_counter()
s1 = solve_1(each)
b = time.perf_counter()
t1.append((b-a)*1000)
a = time.perf_counter()
s2 = solve_2(each)
b = time.perf_counter()
t2.append((b-a)*1000)
for each in s1: #这个二层循环是检查两种方法的结果是否一致的，如不需要，可直接删去
if each not in s2:
print('input',len(each))
pt(each,51,51)
print('s1',(s1))
pt(s1,51,51)
print('s2',(s2))
pt(s2,51,51)
break
print('法一平均用时：%0.4fms\n法二平均用时：%0.4fms\n总共用时%0.4fms'%(sum(t1)/len(t1),sum(t2)/len(t2),sum(t1+t2)))
import math
def fun377(input_list):
if len (input_list) <4:
return input_list
else:
temp_list = input_list
def test_inner():
""""
calc_p 检测点 other_p 其他点的列表
返回值 : True 是内部点, False 不是内部点
检测函数 检测点 所有边都不能夹角 找不到大于 pi的
那么这个点就是内部点,否则就是 位于边界上的点
"""
vector_list = [(i-calc_p, j-calc_p) for i,j in other_p]
deg_list=[]
for x,y in vector_list:
r = (x**2 +y**2)**0.5
deg = math.acos(x/r)
if y<0:
deg = -deg + math.pi *2
deg_list.append(deg)
deg_list.sort()
for i in range(len(deg_list)):
if i == len(deg_list) -1:
if math.pi *2 - deg_list[-1] + deg_list>= math.pi:
break
elif deg_list - deg_list >= math.pi:
break
else:
return True
return False
num = 0 # 从0位置开始 记住上次跳出的 for 循环计数 i 进入下一个for 其实从 i 开始
while num < len(temp_list):
for i in range(num, len(temp_list)):
calc_p = temp_list
other_p = temp_list[:i] + temp_list
if test_inner():
temp_list.remove(calc_p)
num = i
break
else: # 如果for循环 走完了没有被打断说明 现在for里面的都是外部点
return temp_list
return temp_list def f(list1):
def x(list1):
return list1
def y(list1):
return list1
list2 = []
list1 = sorted(list1,key=x)
xmin = list1
xmin_list = []
xmax = list1[-1]
xmax_list = []
for each in list1:
if each == xmin:
list2.append(each)
xmin_list.append(each)
elif each == xmax:
list2.append(each)
xmax_list.append(each)
list1 = sorted(list1,key=y)
ymin = list1
ymin_list = []
ymax = list1[-1]
ymax_list = []
for each in list1:
if each == ymin:
list2.append(each)
ymin_list.append(each)
elif each == ymax:
list2.append(each)
ymax_list.append(each)
xmin_list.sort()
xmax_list.sort()
ymin_list.sort()
ymax_list.sort()
def f1(p1,p2,p3):
if abs((p2-p1)/(p2-p1))<abs((p3-p1)/(p3-p1)):
return 2
elif abs((p2-p1)/(p2-p1))==abs((p3-p1)/(p3-p1)):
return 1
else:
return 0
leftup,leftdown,rightup,rightdown = list1[:],list1[:],list1[:],list1[:]
p1,p2,p3,p4,p5,p6,p7,p8 = ],,ymax],,ymax],],],,ymin],,ymin],]
h1,h2,h3,h4 = [],[],[],[]
while leftup != []:
for each in leftup.copy():
if each>=p2 or each<=p1:
leftup.remove(each)
else:
if f1(p1,p2,each)==2:
h1 = []
h1.append(each)
p2 = each
elif f1(p1,p2,each)==1:
h1.append(each)
if h1 != []:
list2 += h1
h1 = sorted(h1,key=y)
p1 = h1[-1]
p2 = ,ymax]
for m in h1:
leftup.remove(m)
else:
break
while rightup != []:
for each in rightup.copy():
if each<=p3 or each<=p4:
rightup.remove(each)
else:
if f1(p4,p3,each)==2:
h2 = []
h2.append(each)
p3 = each
elif f1(p4,p3,each)==1:
h2.append(each)
if h2 != []:
list2 += h2
h2 = sorted(h2,key=y)
p4 = h2[-1]
p3 = ,ymax]
for m in h2:
rightup.remove(m)
else:
break
while leftdown != []:
for each in leftdown.copy():
if each>=p7 or each>=p8:
leftdown.remove(each)
else:
if f1(p8,p7,each)==2:
h4 = []
h4.append(each)
p7 = each
elif f1(p8,p7,each)==1:
h4.append(each)
if h4 != []:
list2 += h4
h4 = sorted(h4,key=x)
p8 = h4[-1]
p7 = ,ymin]
for m in h4:
leftdown.remove(m)
else:
break
while rightdown != []:
for each in rightdown.copy():
if each<=p6 or each>=p5:
rightdown.remove(each)
else:
if f1(p5,p6,each)==2:
h3 = []
h3.append(each)
p6 = each
elif f1(p5,p6,each)==1:
h3.append(each)
if h3 != []:
list2 += h3
h3 = sorted(h3,key=x)
p5 = h3
p6 = ,ymin]
for m in h3:
rightdown.remove(m)
else:
break
return list2{:10_266:}{:10_266:}{:10_266:} 阴阳神万物主 发表于 2020-4-18 01:56
难度评级：普通
要素分析：数论
随机输入生成器，送给有需要的人：如果觉得好用，麻烦评个分呗
两段代码输入以下数据都会超时：
archlzy 发表于 2020-4-18 11:45
输入以下数据超时：
风魔孤行者 发表于 2020-4-18 16:59
输入 [, , ] 出错
页:
1
[2]