3588.找到最大三角形面积

难度：中等

问题描述：

给你一个二维数组coords，大小为nx2，表示一个无限笛卡尔平面上n个点的坐标。

找出一个最大三角形的两倍面积，其中三角形的三个顶点来自coords中的任意三个点，并且该三角形至少有一条边与x轴或y轴平行。严格地说，如果该三角形的最大面积为A，则返回2*A。

如果不存在这样的三角形，返回-1。

注意，三角形的面积不能为零。

示例1：

输入：coords=[[1,1],[1,2],[3,2],[3,3]]

输出：2

解释：

图中的三角形的底边为1，高为2。因此，它的面积为1/2*底边*高=1。

示例2：

输入：coords=[[1,1],[2,2],[3,3]]

输出：-1

解释：

唯一可能的三角形的顶点是(1,1)、(2,2)和(3,3)。它的任意边都不与x轴或y轴平行。

提示：

1<=n==coords.length<=105

1<=coords[i][0],coords[i][1]<=106

所有coords[i]都是唯一的。

问题分析：

这是一个中规中矩的问题，用正常解决问题的思维逻辑分析即可。

阅读题目中的这一句，“其中三角形的三个顶点来自coords中的任意三个点，并且该三角形至少有一条边与x轴或y轴平行”，故处理步骤如下：

第一步：在coords中找出有哪些点组成的线段是平行于x轴或平行于y轴的，并根据是平行于y轴标记为1，平行于x轴标记为2，组成一个元素为[point1,point2,标记]的列表，这个功能由函数get_parallel_point(points)实现，在主程序中将处理的结果赋值给p2set变量。

第二步：将找到的平行于x轴或平行于y轴的两个点point1和point2从原coords中去掉，剩下的点就可以依次与这两个点组成不同的三角形，且保证这些三角形有一条边与x轴或y轴平行。这个功能由函数get_remain_points(point1,point2,points)实现，在主程序中将处理结果赋值给remain_points变量，然后可以遍历remain_points中的每个点，计算组成不同三角形面积的2倍，并记录其中的最大值。

第三步：如何计算三个点point1、point2和point3组成三角形的面积，这个功能由函数get_triangle_2area(p2,point3)实现。

主程序通过循环，合理调用三个函数即找出coords中最大三角形面积的2倍值。

程序如下：

#在给定的点points中，找出两点平行于x轴或y轴的，设置1标记表示平等于y轴，设置2标记表示平行于x轴，并以列表形式返回
def get_parallel_point(points):n=len(points)p_point=[]for i in range(n-1):point1 = points[i]for j in range(i+1,n):point2=points[j]if point1[0]==point2[0]:p_point.append([point1,point2,1])elif point1[1]==point2[1]:p_point.append([point1,point2,2])return p_point#在给定的点points中，去掉平行的两点之后，返回剩下的点的集合
def get_remain_points(point1,point2,points):return [point for point in points if point!=point1 and point!=point2]#对给定的包含两个平行点point1、point2和标记的数据，以及第三个点point3，计算三角形面积，并返回面积的两倍
def get_triangle_2area(p2,point3):point1=p2[0]point2=p2[1]flag=p2[2]if flag==1:h=abs(point3[0]-point1[0])return abs(point1[1]-point2[1])*helse:h=abs(point3[1]-point1[1])return abs(point1[0]-point2[0])*h#主程序
coords=eval(input('pls input coords='))
#找到所有的平行于x轴或y轴的点对组成的集合
p2set=get_parallel_point(coords)
print(f'在coords中找出平行于x轴或y轴的两点及标记的集合：',p2set)
max_triangle_area=0
for p in p2set:point1=p[0]point2=p[1]remain_points=get_remain_points(point1,point2,coords)print(f'在coords中除掉{point1}和{point2}之后剩下的点的集合为：{remain_points}')for point3 in remain_points:s=get_triangle_2area(p,point3)if s>max_triangle_area:max_triangle_area=sprint(f'由{point1}、{point2}、{point3}组成三角形的面积为{s}，当前最大面积为{max_triangle_area}')
s=-1 if max_triangle_area==0 else max_triangle_area
print('coords中的点无法组成满足条件的三角形！' if s==-1 or s==0 else f'最大三角形的两倍面积为{s}')