Python：每日一题 362
本帖最后由 zltzlt 于 2020-3-29 18:07 编辑今天的题目：
给定包含多个点坐标的数组 points，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
说明：
1. 3 <= len(points) <= 50
2. 不存在重复的点
3. -50 <= points <= 50
4. 结果误差值在 10-6 以内都认为是正确答案。
5. 点的坐标都是整数。
示例：
输入：points = [, , , , ]
输出：2
解释：这五个点如下图所示。
组成的橙色三角形是最大的，面积为 2。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 TJBEST 于 2020-3-30 21:16 编辑
不知道对不对，有点麻烦，可能会有错误，需要楼主检验，我自己测的暂时没问题。
def fun362(points):
def gcd(num1,num2):
while num2:
num1,num2 = num2,num1%num2
return num1
def gcd3(num1,num2,num3):
if num1*num2 == 0:
yue1 = num1+num2
else:
yue1 = gcd(num1,num2)
if num2*num3 == 0:
yue2 = num2+num3
else:
yue2 = gcd(num2,num3)
if yue1 * yue2 == 0:
return yue1+yue2
else:
return gcd(yue1,yue2)
def getLine(point1,point2):
A = points - points
B = points - points
C = points*points -points*points
if A < 0:
A = -A
B = -B
C = -C
elif A == 0:
if B < 0:
B = -B
C = -C
yueshu = gcd3(A,abs(B),abs(C))
return (A//yueshu,B//yueshu,C//yueshu)
def getH(Line,point):#代入距离方程 注意有正负号的
return Line*points+Line*points+Line
def getX(temp,point):#找端点
return points - points
def getDistance(point1,point2):
return (((points-points)**2)+((points-points)**2))**(1/2)
M = len(points)
OutPoint = set()#记录外点
InnerPoint = set()#记录内点
DeadLine = set()#记录直线
index_arr =
S = 0
while len(index_arr) > 2:
if index_arr in InnerPoint:#如果内点 则忽略
pass
elif index_arr in OutPoint:#如果外点 则遍历其他点
temp = index_arr
for eachPoint in index_arr:
if eachPoint in InnerPoint:#内点不考虑
pass
else:#外点 与 未知点需要计算
Line = getLine(temp,eachPoint)#计算两点所在直线方程
if Line in DeadLine:#该直线已经算过
pass
else:
H_arr =
LinePoint = == 0]#直线上点
X_arr = #协助查找端点
if max(H_arr)*min(H_arr) < 0:#内直线
M_Num = max(X_arr)
m_Num = min(X_arr)
Duan1 = LinePoint
Duan2 = LinePoint
InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
else:#外直线
OutPoint |= set(LinePoint)
M_Num = max(X_arr)
m_Num = min(X_arr)
Duan1 = LinePoint
Duan2 = LinePoint
if Duan1 in InnerPoint or Duan2 in InnerPoint:
pass
else:
Standard = ((Line**2)+(Line**2))**(1/2)
H = max()/Standard
Distance = getDistance(Duan1,Duan2)
tempS = (1/2)*(H*Distance)
S = S if tempS <= S else tempS
DeadLine.add(Line)
else:#未知的
temp = index_arr
for eachPoint in index_arr:
if eachPoint in InnerPoint:#内点不考虑
pass
else:#外点 与 未知点需要计算
Line = getLine(temp,eachPoint)#计算两点所在直线方程
if Line in DeadLine:#该直线已经算过
pass
else:
H_arr =
LinePoint = == 0]#直线上点
X_arr = #协助查找端点
if max(H_arr)*min(H_arr) < 0:#内直线
M_Num = max(X_arr)
m_Num = min(X_arr)
Duan1 = LinePoint
Duan2 = LinePoint
InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
else:#外直线
OutPoint |= set(LinePoint)
M_Num = max(X_arr)
m_Num = min(X_arr)
Duan1 = LinePoint
Duan2 = LinePoint
if Duan1 in InnerPoint or Duan2 in InnerPoint:
pass
else:
Standard = ((Line**2)+(Line**2))**(1/2)
H = max()/Standard
Distance = getDistance(Duan1,Duan2)
tempS = (1/2)*(H*Distance)
S = S if tempS <= S else tempS
DeadLine.add(Line)
if temp in InnerPoint:
break
index_arr = index_arr
return S 问个问题，横纵坐标都是整数吗？ TJBEST 发表于 2020-3-29 17:55
问个问题，横纵坐标都是整数吗？
见帖子 “说明” zltzlt 发表于 2020-3-29 17:59
见帖子 “说明”
那就是实数吧 TJBEST 发表于 2020-3-29 18:05
那就是实数吧
是整数，刚刚漏了一条 本帖最后由 BngThea 于 2020-3-29 19:55 编辑
def fun362(lst):
length=len(lst)
area = 0
for i in range(length-2):
for j in range(i+1,length-1):
for k in range(j+1,length):
(x1,y1),(x2,y2),(x3,y3)=lst,lst,lst
tmp = abs((1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))
if area < tmp:
area = tmp
return area 本帖最后由 kinkon 于 2020-3-29 20:05 编辑
form itertools import combinations as cb
def f361(points):
return max(abs((x0-x2)*(y1-y2)-(x1-x2)*(y0-y2)) for (x0,y0),(x1,y1),(x2,y2) in cb(points,3))/2 from math import sqrt, pow
# S = sqrt(p(p-a)(p-b)(p-c)) when p = (a + b + c) / 2
def daily362(points: list) -> int:
area = []
for i in range(len(points)):
for j in range(len(points)):
for k in range(len(points)):
if i != j != k:
a = get_Length(points, points)
b = get_Length(points, points)
c = get_Length(points, points)
if is_Triangle():
area.append(get_Area())
area.sort()
return area[-1]
def get_Length(p1: list, p2: list) -> float:
return sqrt(pow(p2-p1, 2) + pow(p2-p1, 2))
def is_Triangle(l: list) -> bool:
l.sort()
if l + l > l:
return True
return False
def get_Area(l: list) -> float:
p = (l + l + l) / 2
return sqrt(p * (p-l)* (p-l)* (p-l))
写个最笨的，等大佬有好的思路 from itertools import permutations as p
def f362(points):
m=0
for a,b,c in p(points,3):
xa,ya=a
xb,yb=b
xc,yc=c
m=max(m,(xa*(yb-yc)+xb*(yc-ya)+xc*(ya-yb))/2)
return m
本帖最后由 mdphd 于 2020-3-29 20:50 编辑
import math
def area(A,B,C):
a = (A - B) ** 2 + (A - B) ** 2
b = (B - C) ** 2 + (B - C) ** 2
c = (C - A) ** 2 + (C - A) ** 2
s = math.sqrt(- a**2 - b**2 - c**2 + 2*a*b +2*b*c + 2*c*a) / 4
return s
def f362(points):
points.sort()
keysmax = list(map(lambda x:points,range(len(points))))
dictmax = dict(zip(keysmax,points))
points.sort(reverse = True)
keysmin = list(map(lambda x:points,range(len(points))))
dictmin = dict(zip(keysmin,points))
out = list(dictmax.values()) + list(dictmin.values())
out =
n = len(out)
S = []
for i in range(0, n):
for j in range(i,n):
for k in range(j,n):
S.append(area(out,out,out))
return max(S) 一行代码from itertools import permutations as p
def f362(points:list)->float:
return max([(1/2)*(x*y+y*z+z*x-x*z-y*x-z*y) for x,y,z in p(points,3)]) from itertools import combinations as p
def func362(points):
s = 0
for a,b,c in p(points,3):
x1,y1 = a
x2,y2 = b
x3,y3 = c
s=max(s, abs((1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)))
return s 本帖最后由 旅途Z 于 2020-3-31 17:46 编辑
import numpy as np
def calc_area(array, index):
array = np.array(array)
a = array]
b = array]
c = array]
x = b - a
y = c - a
return abs(x * y - x * y)
def get_triangle(point_array):
length = len(point_array)
points = combinations(range(length), 3)
max_area = 0
for point in points:
area = calc_area(point_array, point)
if area >= max_area:
max_area = area
return max_area/2 def cals(points):
max=-1
for i in points :
for j in points :
for k in points :
s = i*j-i*k+j*k-j*i+k*i-j*j
if(s>max):
max = s
return(max//2) 学c中{:10_265:} def f362(points):
import itertools
import math
three_points=itertools.combinations(points, 3)
area=[]
for i in three_points:
a = math.sqrt((i - i) * (i - i) + (i - i) * (i - i))
b = math.sqrt((i - i) * (i - i) + (i - i) * (i - i))
c = math.sqrt((i - i) * (i - i) + (i - i) * (i - i))
area.append((math.sqrt((a+b+c)*(a+b-c)*(a+c-b)*(b+c-a)))/4)
return max(area) 楼主 今天刚开始做这题，感觉有点难。@zltzlt我最晚晚上9点可以吗？别封题 本帖最后由 蒋博文 于 2020-3-30 16:47 编辑
def fun362(points):
result = 0
for i in range(len(points)):
for j in range(i+1, len(points)):
for z in range(j+1, len(points)):
max_area = (points * points + points * points +
points * points - points * points -
points * points - points * points) / 2
result = max(result, abs(max_area))
return result TJBEST 发表于 2020-3-30 14:21
楼主 今天刚开始做这题，感觉有点难。@zltzlt我最晚晚上9点可以吗？别封题
好