力扣算法题：平分正方形（算法小白每日一题）

题号面试题16.13 平分正方形题目内容给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。每个正方形的数据square包含3个数值正方形的左下顶点坐标[X,Y] [square[0],square[1]]以及正方形的边长square[2]。所求直线穿过两个正方形会形成4个交点请返回4个交点形成线段的两端点坐标两个端点即为4个交点中距离最远的2个点这2个点所连成的线段一定会穿过另外2个交点。2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2}要求若X1 ! X2需保证X1 X2否则需保证Y1 Y2。若同时有多条直线满足要求则选择斜率最大的一条计算并返回与Y轴平行的直线视为斜率无穷大。示例输入square1 {-1, -1, 2} square2 {0, -1, 2}输出{-1,0,2,0}解释直线 y 0 能将两个正方形同时分为等面积的两部分返回的两线段端点为[-1,0]和[2,0]解题过程及思路第一眼看到题目一脸懵想了五分钟没思路看了下提示后豁然开朗这套题基本上是纯粹的数学题利用高中的知识求解。由题意得所求的直线平分两个正方形而平分正方形的直线一定过正方形的中点所以题目可以转化为求过两个正方形中点的直线与两个正方形的交点取最远的两个。分情况讨论如下设中点的坐标分别为C1(x1, y1)C2(x2, y2)则直线坐标可以表示为1、若两正方形中点的X轴坐标相等则平分线为垂直于X轴的直线这种情况包含了两中点重合的情况因为题目要求如果有多条直线满足要求则选择斜率最大的一条。2、若两正方形中点的X轴坐标不相等则需按直线的斜率考虑a. 直线斜率的绝对值大于1时此时情况如图此时交点的Y坐标已知X坐标未知。b. 直线斜率的绝对值小于1时此时情况如图此时交点的X坐标已知Y坐标未知。c. 直线斜率的绝对值恰好等于1时可以在上述两种斜率中任选一种即可。使用python编写代码如下代码基本上算纯数学语言转化过来较为繁琐仅提供一个思路可以找找其他大佬的代码或者用ai生成更简介的代码实现。def cut_squares(self, square1: List[int], square2: List[int]) - List[float]: # 先求两个正方形的中心点因为平分正方形的直线一定过其中心。 square1_center [float(square1[0]) float(square1[2]) / 2, float(square1[1]) float(square1[2] / 2)] square2_center [float(square2[0]) float(square2[2]) / 2, float(square2[1]) float(square2[2] / 2)] # 如果两个正方形X轴坐标相等则其斜率最大的平分线为垂直与Y轴的直线 if square1_center[0] square2_center[0]: lower_x square1_center[0] lower_y min(square1[1], square2[1]) higher_x square1_center[0] higher_y max(square1[1] square1[2], square2[1] square2[2]) result [lower_x, lower_y, higher_x, higher_y] return result # 如果平分线不垂直y轴则需要求连接两点的直线 k ((square1_center[1] - square2_center[1]) / (square1_center[0] - square2_center[0])) # 斜率的绝对值大于1时 if k ** 2 1: y1 min(square1[1], square2[1]) x1 (y1 - square1_center[1])*(square1_center[0] - square2_center[0])/(square1_center[1] - square2_center[1]) square1_center[0] y2 max(square1[1] square1[2], square2[1] square2[2]) x2 (y2 - square1_center[1])*(square1_center[0] - square2_center[0])/(square1_center[1] - square2_center[1]) square1_center[0] # 需要判断斜率的正负 if k 0: result [x1, y1, x2, y2] return result else: result [x2, y2, x1, y1,] return result #斜率的绝对值小于1时 else: lower_x min(square1[0], square2[0]) lower_y (lower_x - square1_center[0])*(square1_center[1] - square2_center[1])/(square1_center[0] - square2_center[0]) square1_center[1] higher_x max(square1[0] square1[2], square2[0] square2[2]) higher_y (higher_x - square1_center[0])*(square1_center[1] - square2_center[1])/(square1_center[0] - square2_center[0]) square1_center[1] result [lower_x, lower_y, higher_x, higher_y] return result关注我从零开始的算法小白之路。