[已解决]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 ？

敲错啦

from 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

跳转到最佳答案楼层

TJBEST

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

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[point2][1] - points[point1][1]
        B = points[point1][0] - points[point2][0]
        C = points[point2][0]*points[point1][1] -points[point1][0]*points[point2][1]
        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[0]*points[point][0]+Line[1]*points[point][1]+Line[2]
    def getX(temp,point):#找端点
        return points[temp][0] - points[point][0]
    def getDistance(point1,point2):
        return (((points[point1][0]-points[point2][0])**2)+((points[point1][1]-points[point2][1])**2))**(1/2)
    M = len(points)
    OutPoint = set()#记录外点
    InnerPoint = set()#记录内点
    DeadLine = set()#记录直线
    index_arr = [i for i in range(0,M)]
    S = 0
    while len(index_arr) > 2:
        if index_arr[0] in InnerPoint:#如果内点 则忽略
            pass
        elif index_arr[0] in OutPoint:#如果外点 则遍历其他点
            temp = index_arr[0]
            for eachPoint in index_arr[1:]:
                if eachPoint in InnerPoint:#内点不考虑
                    pass
                else:#外点 与 未知点需要计算
                    Line = getLine(temp,eachPoint)#计算两点所在直线方程
                    if Line in DeadLine:#该直线已经算过
                        pass
                    else:
                        H_arr = [getH(Line,i) for i in range(0,M)]
                        LinePoint = [i for i in range(0,M) if H_arr[i] == 0]#直线上点
                        X_arr = [getX(temp,i) for i in LinePoint]#协助查找端点
                        if max(H_arr)*min(H_arr) < 0:#内直线
                            M_Num = max(X_arr)
                            m_Num = min(X_arr)
                            Duan1 = LinePoint[X_arr.index(M_Num)]
                            Duan2 = LinePoint[X_arr.index(m_Num)]
                            InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
                        else:#外直线
                            OutPoint |= set(LinePoint)
                            M_Num = max(X_arr)
                            m_Num = min(X_arr)
                            Duan1 = LinePoint[X_arr.index(M_Num)]
                            Duan2 = LinePoint[X_arr.index(m_Num)]
                        if Duan1 in InnerPoint or Duan2 in InnerPoint:
                            pass
                        else:
                            Standard = ((Line[0]**2)+(Line[1]**2))**(1/2)
                            H = max([abs(max(H_arr)),abs(min(H_arr))])/Standard
                            Distance = getDistance(Duan1,Duan2)
                            tempS = (1/2)*(H*Distance)
                            S = S if tempS <= S else tempS
                            DeadLine.add(Line)
        else:#未知的
            temp = index_arr[0]
            for eachPoint in index_arr[1:]:
                if eachPoint in InnerPoint:#内点不考虑
                    pass
                else:#外点 与 未知点需要计算
                    Line = getLine(temp,eachPoint)#计算两点所在直线方程
                    if Line in DeadLine:#该直线已经算过
                        pass
                    else:
                        H_arr = [getH(Line,i) for i in range(0,M)]
                        LinePoint = [i for i in range(0,M) if H_arr[i] == 0]#直线上点
                        X_arr = [getX(temp,i) for i in LinePoint]#协助查找端点
                        if max(H_arr)*min(H_arr) < 0:#内直线
                            M_Num = max(X_arr)
                            m_Num = min(X_arr)
                            Duan1 = LinePoint[X_arr.index(M_Num)]
                            Duan2 = LinePoint[X_arr.index(m_Num)]
                            InnerPoint |= (set(LinePoint) - {Duan1,Duan2})
                        else:#外直线
                            OutPoint |= set(LinePoint)
                            M_Num = max(X_arr)
                            m_Num = min(X_arr)
                            Duan1 = LinePoint[X_arr.index(M_Num)]
                            Duan2 = LinePoint[X_arr.index(m_Num)]
                        if Duan1 in InnerPoint or Duan2 in InnerPoint:
                            pass
                        else:
                            Standard = ((Line[0]**2)+(Line[1]**2))**(1/2)
                            H = max([abs(max(H_arr)),abs(min(H_arr))])/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[1:]
    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

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[i],lst[j],lst[k]
                tmp = abs((1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))
                if area < tmp:
                    area = tmp
    return area

kinkon

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

March2615

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[i], points[j])
                    b = get_Length(points[j], points[k])
                    c = get_Length(points[k], points[i])
                    if is_Triangle([a, b, c]):
                        area.append(get_Area([a, b, c]))
    area.sort()
    return area[-1]



def get_Length(p1: list, p2: list) -> float:
    return sqrt(pow(p2[1]-p1[1], 2) + pow(p2[0]-p1[0], 2))


def is_Triangle(l: list) -> bool:
    l.sort()
    if l[0] + l[1] > l[2]:
        return True
    return False


def get_Area(l: list) -> float:
    p = (l[0] + l[1] + l[2]) / 2
    return sqrt(p * (p-l[0])* (p-l[1])* (p-l[2]))

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

塔利班

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

import math
def area(A,B,C):
    a = (A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2
    b = (B[0] - C[0]) ** 2 + (B[1] - C[1]) ** 2
    c = (C[0] - A[0]) ** 2 + (C[1] - A[1]) ** 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[x][0],range(len(points))))
    dictmax = dict(zip(keysmax,points))
    points.sort(reverse = True)
    keysmin = list(map(lambda x:points[x][0],range(len(points))))
    dictmin = dict(zip(keysmin,points))
    out = list(dictmax.values()) + list(dictmin.values())
    out = [list(t) for t in set(tuple(_) for _ in 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[i],out[j],out[k]))
    return max(S)

ouyunfu

一行代码

from itertools import permutations as p        
def f362(points:list)->float:
    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

def f362(points):
    import itertools
    import math
    three_points=itertools.combinations(points, 3)
    area=[]
    for i in three_points:
        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]))
        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]))
        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]))
        area.append((math.sqrt((a+b+c)*(a+b-c)*(a+c-b)*(b+c-a)))/4)
    return max(area)

TJBEST

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

蒋博文

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[i][0] * points[j][1] + points[j][0] * points[z][1] + 
                        points[z][0] * points[i][1] - points[i][0] * points[z][1] - 
                        points[j][0] * points[i][1] - points[z][0] * points[j][1]) / 2
                result = max(result, abs(max_area))
        return result

zltzlt

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

好