网站的记住密码功能怎么做,快速的可视化平台,有赞微商城登录入口,在线商城建设3588.找到最大三角形面积难度#xff1a;中等问题描述#xff1a;给你一个二维数组coords#xff0c;大小为nx2#xff0c;表示一个无限笛卡尔平面上n个点的坐标。找出一个最大三角形的两倍面积#xff0c;其中三角形的三个顶点来自coords中的任意三个点#xff0c;并且该…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轴平行。提示1ncoords.length1051coords[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):nlen(points)p_point[]for i in range(n-1):point1 points[i]for j in range(i1,n):point2points[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):point1p2[0]point2p2[1]flagp2[2]if flag1:habs(point3[0]-point1[0])return abs(point1[1]-point2[1])*helse:habs(point3[1]-point1[1])return abs(point1[0]-point2[0])*h#主程序
coordseval(input(pls input coords))
#找到所有的平行于x轴或y轴的点对组成的集合
p2setget_parallel_point(coords)
print(f在coords中找出平行于x轴或y轴的两点及标记的集合,p2set)
max_triangle_area0
for p in p2set:point1p[0]point2p[1]remain_pointsget_remain_points(point1,point2,coords)print(f在coords中除掉{point1}和{point2}之后剩下的点的集合为{remain_points})for point3 in remain_points:sget_triangle_2area(p,point3)if smax_triangle_area:max_triangle_areasprint(f由{point1}、{point2}、{point3}组成三角形的面积为{s}当前最大面积为{max_triangle_area})
s-1 if max_triangle_area0 else max_triangle_area
print(coords中的点无法组成满足条件的三角形 if s-1 or s0 else f最大三角形的两倍面积为{s})运行实例一pls input coords[[1,1],[2,3],[3,5],[7,4]]在coords中找出平行于x轴或y轴的两点及标记的集合 []coords中的点无法组成满足条件的三角形运行实例二pls input coords[[3,3],[7,3],[4,8]]在coords中找出平行于x轴或y轴的两点及标记的集合 [[[3, 3], [7, 3], 2]]在coords中除掉[3, 3]和[7, 3]之后剩下的点的集合为[[4, 8]]由[3, 3]、[7, 3]、[4, 8]组成三角形的面积为20当前最大面积为20最大三角形的两倍面积为20运行实例三pls input coords[[1,1],[5,1],[5,3],[7,3],[9,4]]在coords中找出平行于x轴或y轴的两点及标记的集合 [[[1, 1], [5, 1], 2], [[5, 1], [5, 3], 1], [[5, 3], [7, 3], 2]]在coords中除掉[1, 1]和[5, 1]之后剩下的点的集合为[[5, 3], [7, 3], [9, 4]]由[1, 1]、[5, 1]、[5, 3]组成三角形的面积为8当前最大面积为8由[1, 1]、[5, 1]、[7, 3]组成三角形的面积为8当前最大面积为8由[1, 1]、[5, 1]、[9, 4]组成三角形的面积为12当前最大面积为12在coords中除掉[5, 1]和[5, 3]之后剩下的点的集合为[[1, 1], [7, 3], [9, 4]]由[5, 1]、[5, 3]、[1, 1]组成三角形的面积为8当前最大面积为12由[5, 1]、[5, 3]、[7, 3]组成三角形的面积为4当前最大面积为12由[5, 1]、[5, 3]、[9, 4]组成三角形的面积为8当前最大面积为12在coords中除掉[5, 3]和[7, 3]之后剩下的点的集合为[[1, 1], [5, 1], [9, 4]]由[5, 3]、[7, 3]、[1, 1]组成三角形的面积为4当前最大面积为12由[5, 3]、[7, 3]、[5, 1]组成三角形的面积为4当前最大面积为12由[5, 3]、[7, 3]、[9, 4]组成三角形的面积为2当前最大面积为12最大三角形的两倍面积为12运行实例四pls input coords[[1,1],[2,1],[4,1]]在coords中找出平行于x轴或y轴的两点及标记的集合 [[[1, 1], [2, 1], 2], [[1, 1], [4, 1], 2], [[2, 1], [4, 1], 2]]在coords中除掉[1, 1]和[2, 1]之后剩下的点的集合为[[4, 1]]由[1, 1]、[2, 1]、[4, 1]组成三角形的面积为0当前最大面积为0在coords中除掉[1, 1]和[4, 1]之后剩下的点的集合为[[2, 1]]由[1, 1]、[4, 1]、[2, 1]组成三角形的面积为0当前最大面积为0在coords中除掉[2, 1]和[4, 1]之后剩下的点的集合为[[1, 1]]由[2, 1]、[4, 1]、[1, 1]组成三角形的面积为0当前最大面积为0coords中的点无法组成满足条件的三角形解决问题可能有不同的方法但如果能够抓住问题关键可能事半功倍。
