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

zltzlt

今天的题目：

给定包含多个点坐标的数组 points，从其中取三个点组成三角形，返回能组成的最大三角形的面积。

说明：
1. 3 <= len(points) <= 50
2. 不存在重复的点
3. -50 <= points[c][d] <= 50
4. 结果误差值在 10^-6 以内都认为是正确答案。
5. 点的坐标都是整数。

示例：

输入：points = [[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]
输出：2
解释：这五个点如下图所示。



组成的橙色三角形是最大的，面积为 2。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-3-31 18:11:15

zltzlt 发表于 2020-3-31 17:22
form ？

敲错啦

1. from itertools import combinations as cb
   
2. def f361(points):
   
3.     return max(abs((x0-x2)*(y1-y2)-(x1-x2)*(y0-y2)) for (x0,y0),(x1,y1),(x2,y2) in cb(points,3))/2

复制代码

跳转到最佳答案楼层

TJBEST

不知道对不对，有点麻烦，可能会有错误，需要楼主检验，我自己测的暂时没问题。

1. def fun362(points):
   
2.     def gcd(num1,num2):
   
3.         while num2:
   
4.             num1,num2 = num2,num1%num2
   
5.         return num1
   
6.     def gcd3(num1,num2,num3):
   
7.         if num1*num2 == 0:
   
8.             yue1 = num1+num2
   
9.         else:
   
10.             yue1 = gcd(num1,num2)
    
11.         if num2*num3 == 0:
    
12.             yue2 = num2+num3
    
13.         else:
    
14.             yue2 = gcd(num2,num3)
    
15.         if yue1 * yue2 == 0:
    
16.             return yue1+yue2
    
17.         else:
    
18.             return gcd(yue1,yue2)
    
19.     def getLine(point1,point2):
    
20.         A = points[point2][1] - points[point1][1]
    
21.         B = points[point1][0] - points[point2][0]
    
22.         C = points[point2][0]*points[point1][1] -points[point1][0]*points[point2][1]
    
23.         if A < 0:
    
24.             A = -A
    
25.             B = -B
    
26.             C = -C
    
27.         elif A == 0:
    
28.             if B < 0:
    
29.                 B = -B
    
30.                 C = -C
    
31.         yueshu = gcd3(A,abs(B),abs(C))
    
32.         return (A//yueshu,B//yueshu,C//yueshu)
    
33.     def getH(Line,point):#代入距离方程 注意有正负号的
    
34.         return Line[0]*points[point][0]+Line[1]*points[point][1]+Line[2]
    
35.     def getX(temp,point):#找端点
    
36.         return points[temp][0] - points[point][0]
    
37.     def getDistance(point1,point2):
    
38.         return (((points[point1][0]-points[point2][0])**2)+((points[point1][1]-points[point2][1])**2))**(1/2)
    
39.     M = len(points)
    
40.     OutPoint = set()#记录外点
    
41.     InnerPoint = set()#记录内点
    
42.     DeadLine = set()#记录直线
    
43.     index_arr = [i for i in range(0,M)]
    
44.     S = 0
    
45.     while len(index_arr) > 2:
    
46.         if index_arr[0] in InnerPoint:#如果内点 则忽略
    
47.             pass
    
48.         elif index_arr[0] in OutPoint:#如果外点 则遍历其他点
    
49.             temp = index_arr[0]
    
50.             for eachPoint in index_arr[1:]:
    
51.                 if eachPoint in InnerPoint:#内点不考虑
    
52.                     pass
    
53.                 else:#外点 与 未知点需要计算
    
54.                     Line = getLine(temp,eachPoint)#计算两点所在直线方程
    
55.                     if Line in DeadLine:#该直线已经算过
    
56.                         pass
    
57.                     else:
    
58.                         H_arr = [getH(Line,i) for i in range(0,M)]
    
59.                         LinePoint = [i for i in range(0,M) if H_arr[i] == 0]#直线上点
    
60.                         X_arr = [getX(temp,i) for i in LinePoint]#协助查找端点
    
61.                         if max(H_arr)*min(H_arr) < 0:#内直线
    
62.                             M_Num = max(X_arr)
    
63.                             m_Num = min(X_arr)
    
64.                             Duan1 = LinePoint[X_arr.index(M_Num)]
    
65.                             Duan2 = LinePoint[X_arr.index(m_Num)]
    
66.                             InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
    
67.                         else:#外直线
    
68.                             OutPoint |= set(LinePoint)
    
69.                             M_Num = max(X_arr)
    
70.                             m_Num = min(X_arr)
    
71.                             Duan1 = LinePoint[X_arr.index(M_Num)]
    
72.                             Duan2 = LinePoint[X_arr.index(m_Num)]
    
73.                         if Duan1 in InnerPoint or Duan2 in InnerPoint:
    
74.                             pass
    
75.                         else:
    
76.                             Standard = ((Line[0]**2)+(Line[1]**2))**(1/2)
    
77.                             H = max([abs(max(H_arr)),abs(min(H_arr))])/Standard
    
78.                             Distance = getDistance(Duan1,Duan2)
    
79.                             tempS = (1/2)*(H*Distance)
    
80.                             S = S if tempS <= S else tempS
    
81.                             DeadLine.add(Line)
    
82.         else:#未知的
    
83.             temp = index_arr[0]
    
84.             for eachPoint in index_arr[1:]:
    
85.                 if eachPoint in InnerPoint:#内点不考虑
    
86.                     pass
    
87.                 else:#外点 与 未知点需要计算
    
88.                     Line = getLine(temp,eachPoint)#计算两点所在直线方程
    
89.                     if Line in DeadLine:#该直线已经算过
    
90.                         pass
    
91.                     else:
    
92.                         H_arr = [getH(Line,i) for i in range(0,M)]
    
93.                         LinePoint = [i for i in range(0,M) if H_arr[i] == 0]#直线上点
    
94.                         X_arr = [getX(temp,i) for i in LinePoint]#协助查找端点
    
95.                         if max(H_arr)*min(H_arr) < 0:#内直线
    
96.                             M_Num = max(X_arr)
    
97.                             m_Num = min(X_arr)
    
98.                             Duan1 = LinePoint[X_arr.index(M_Num)]
    
99.                             Duan2 = LinePoint[X_arr.index(m_Num)]
    
100.                             InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
     
101.                         else:#外直线
     
102.                             OutPoint |= set(LinePoint)
     
103.                             M_Num = max(X_arr)
     
104.                             m_Num = min(X_arr)
     
105.                             Duan1 = LinePoint[X_arr.index(M_Num)]
     
106.                             Duan2 = LinePoint[X_arr.index(m_Num)]
     
107.                         if Duan1 in InnerPoint or Duan2 in InnerPoint:
     
108.                             pass
     
109.                         else:
     
110.                             Standard = ((Line[0]**2)+(Line[1]**2))**(1/2)
     
111.                             H = max([abs(max(H_arr)),abs(min(H_arr))])/Standard
     
112.                             Distance = getDistance(Duan1,Duan2)
     
113.                             tempS = (1/2)*(H*Distance)
     
114.                             S = S if tempS <= S else tempS
     
115.                             DeadLine.add(Line)
     
116.                         if temp in InnerPoint:
     
117.                             break
     
118.         index_arr = index_arr[1:]
     
119.     return S

复制代码

TJBEST

问个问题，横纵坐标都是整数吗？

zltzlt

TJBEST 发表于 2020-3-29 17:55
问个问题，横纵坐标都是整数吗？

见帖子 “说明”

TJBEST

zltzlt 发表于 2020-3-29 17:59
见帖子 “说明”

那就是实数吧

zltzlt

TJBEST 发表于 2020-3-29 18:05
那就是实数吧

是整数，刚刚漏了一条

BngThea

1. def fun362(lst):
   
2.     length=len(lst)
   
3.     area = 0
   
4.     for i in range(length-2):
   
5.         for j in range(i+1,length-1):
   
6.             for k in range(j+1,length):
   
7.                 (x1,y1),(x2,y2),(x3,y3)=lst[i],lst[j],lst[k]
   
8.                 tmp = abs((1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))
   
9.                 if area < tmp:
   
10.                     area = tmp
    
11.     return area

复制代码

kinkon

1. form itertools import combinations as cb
   
2. def f361(points):
   
3.     return max(abs((x0-x2)*(y1-y2)-(x1-x2)*(y0-y2)) for (x0,y0),(x1,y1),(x2,y2) in cb(points,3))/2

复制代码

March2615

1. from math import sqrt, pow
   
2. # S = sqrt(p(p-a)(p-b)(p-c)) when p = (a + b + c) / 2
   
3. 
   
4. 
   
5. def daily362(points: list) -> int:
   
6.     area = []
   
7.     for i in range(len(points)):
   
8.         for j in range(len(points)):
   
9.             for k in range(len(points)):
   
10.                 if i != j != k:
    
11.                     a = get_Length(points[i], points[j])
    
12.                     b = get_Length(points[j], points[k])
    
13.                     c = get_Length(points[k], points[i])
    
14.                     if is_Triangle([a, b, c]):
    
15.                         area.append(get_Area([a, b, c]))
    
16.     area.sort()
    
17.     return area[-1]
    
18. 
    
19. 
    
20. 
    
21. def get_Length(p1: list, p2: list) -> float:
    
22.     return sqrt(pow(p2[1]-p1[1], 2) + pow(p2[0]-p1[0], 2))
    
23. 
    
24. 
    
25. def is_Triangle(l: list) -> bool:
    
26.     l.sort()
    
27.     if l[0] + l[1] > l[2]:
    
28.         return True
    
29.     return False
    
30. 
    
31. 
    
32. def get_Area(l: list) -> float:
    
33.     p = (l[0] + l[1] + l[2]) / 2
    
34.     return sqrt(p * (p-l[0])* (p-l[1])* (p-l[2]))

复制代码

写个最笨的，等大佬有好的思路

塔利班

1. from itertools import permutations as p
   
2. def f362(points):
   
3.     m=0
   
4.     for a,b,c in p(points,3):
   
5.         xa,ya=a
   
6.         xb,yb=b
   
7.         xc,yc=c
   
8.         m=max(m,(xa*(yb-yc)+xb*(yc-ya)+xc*(ya-yb))/2)
   
9.     return m

复制代码

mdphd

1. import math
   
2. def area(A,B,C):
   
3.     a = (A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2
   
4.     b = (B[0] - C[0]) ** 2 + (B[1] - C[1]) ** 2
   
5.     c = (C[0] - A[0]) ** 2 + (C[1] - A[1]) ** 2
   
6.     s = math.sqrt(- a**2 - b**2 - c**2 + 2*a*b +2*b*c + 2*c*a) / 4
   
7.     return s
   
8. def f362(points):
   
9.     points.sort()
   
10.     keysmax = list(map(lambda x:points[x][0],range(len(points))))
    
11.     dictmax = dict(zip(keysmax,points))
    
12.     points.sort(reverse = True)
    
13.     keysmin = list(map(lambda x:points[x][0],range(len(points))))
    
14.     dictmin = dict(zip(keysmin,points))
    
15.     out = list(dictmax.values()) + list(dictmin.values())
    
16.     out = [list(t) for t in set(tuple(_) for _ in out)]
    
17.     n = len(out)
    
18.     S = []
    
19.     for i in range(0, n):
    
20.         for j in range(i,n):
    
21.             for k in range(j,n):
    
22.                 S.append(area(out[i],out[j],out[k]))
    
23.     return max(S)

复制代码

ouyunfu

一行代码

1. from itertools import permutations as p        
   
2. def f362(points:list)->float:
   
3.     return max([(1/2)*(x[0]*y[1]+y[0]*z[1]+z[0]*x[1]-x[0]*z[1]-y[0]*x[1]-z[0]*y[1]) for x,y,z in p(points,3)])

复制代码

whosyourdaddy

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

import numpy as np


def calc_area(array, index):
    array = np.array(array)
    a = array[index[0]]
    b = array[index[1]]
    c = array[index[2]]
    x = b - a
    y = c - a
    return abs(x[0] * y[1] - x[1] * y[0])


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

Joy187

def cals(points):
     max=-1
     for i in points :
          for j in points :
               for k in points :
                    s = i[0]*j[1]-i[0]*k[1]+j[0]*k[1]-j[0]*i[1]+k[0]*i[1]-j[0]*j[1]
                    if(s>max):
                        max = s
     return(max//2)

以后and未来

学c中

l0stparadise

1. def f362(points):
   
2.     import itertools
   
3.     import math
   
4.     three_points=itertools.combinations(points, 3)
   
5.     area=[]
   
6.     for i in three_points:
   
7.         a = math.sqrt((i[0][0] - i[1][0]) * (i[0][0] - i[1][0]) + (i[0][1] - i[1][1]) * (i[0][1] - i[1][1]))
   
8.         b = math.sqrt((i[0][0] - i[2][0]) * (i[0][0] - i[2][0]) + (i[0][1] - i[2][1]) * (i[0][1] - i[2][1]))
   
9.         c = math.sqrt((i[1][0] - i[2][0]) * (i[1][0] - i[2][0]) + (i[1][1] - i[2][1]) * (i[1][1] - i[2][1]))
   
10.         area.append((math.sqrt((a+b+c)*(a+b-c)*(a+c-b)*(b+c-a)))/4)
    
11.     return max(area)

复制代码

TJBEST

楼主 今天刚开始做这题，感觉有点难。@zltzlt  我最晚晚上9点可以吗？别封题

蒋博文

1. def fun362(points):
   
2.     result = 0
   
3.     for i in range(len(points)):
   
4.         for j in range(i+1, len(points)):
   
5.             for z in range(j+1, len(points)):
   
6.                 max_area = (points[i][0] * points[j][1] + points[j][0] * points[z][1] +
   
7.                         points[z][0] * points[i][1] - points[i][0] * points[z][1] -
   
8.                         points[j][0] * points[i][1] - points[z][0] * points[j][1]) / 2
   
9.                 result = max(result, abs(max_area))
   
10.         return result

复制代码

zltzlt

TJBEST 发表于 2020-3-30 14:21
楼主 今天刚开始做这题，感觉有点难。@zltzlt  我最晚晚上9点可以吗？别封题

好