平分正方形

标签: 几何 数学

难度: Medium

给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 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]

提示：

  • square.length == 3
  • square[2] > 0

Submission

运行时间: 20 ms

内存: 16.2 MB

class Solution:
    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:
        get_x = lambda y: (y - b) / k
        get_y = lambda x: k * x + b
        
        (x1, y1, l1), (x2, y2, l2) = square1, square2
        c1 = (x1 + l1 / 2, y1 + l1 / 2)
        c2 = (x2 + l2 / 2, y2 + l2 / 2)
        dy, dx = c2[1] - c1[1], c2[0] - c1[0]
        points = []
        if dx == 0:
            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]
        else:
            k = dy / dx
            b = c1[1] - c1[0] * k
            if -1 <= k <= 1:
                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), 
                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]
            else:
                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),
                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]
        points = sorted(points)
        return [*points[0], *points[-1]]

Explain

首先，计算出每个正方形的中心点坐标。使用这两个中心点来确定一条直线，这条直线将通过两个正方形的中心，从而将每个正方形分割为面积相等的两部分。计算直线的斜率 k = (y2中心 - y1中心) / (x2中心 - x1中心) 和截距 b。使用这个直线方程来计算四个交点：两个交点在第一个正方形的边界上，另外两个在第二个正方形的边界上。这些交点取决于直线的斜率。如果斜率的绝对值在-1到1之间（包括），则交点在水平边界上；如果斜率的绝对值大于1，则交点在垂直边界上。最后，从这四个交点中选出最远的两个点作为最终的答案。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:
        # 计算直线方程 y = kx + b 的 k 和 b
        get_x = lambda y: (y - b) / k
        get_y = lambda x: k * x + b
        
        (x1, y1, l1), (x2, y2, l2) = square1, square2
        # 计算每个正方形的中心
        c1 = (x1 + l1 / 2, y1 + l1 / 2)
        c2 = (x2 + l2 / 2, y2 + l2 / 2)
        dy, dx = c2[1] - c1[1], c2[0] - c1[0]
        points = []
        if dx == 0:  # 处理垂直直线情况
            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]
        else:
            k = dy / dx
            b = c1[1] - c1[0] * k
            if -1 <= k <= 1:  # 根据斜率决定使用 x 或 y 的边界计算交点
                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), 
                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]
            else:
                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),
                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]
        points = sorted(points)  # 排序找到最远的两个点
        return [*points[0], *points[-1]]

Explore

当两个正方形中心点的横坐标相同时，这意味着直线是垂直的，斜率是无限大。在这种情况下，无法使用常规的斜率和截距公式来描述这条直线。因此，我选择了直接使用中心点的横坐标作为直线的定义，即 x = 常数。这样，直线方程简化为 x = c1[0]，其中 c1[0] 是第一个正方形中心的横坐标。这种处理方式是直接且易于理解的，它能有效地表示垂直直线并且完美地解决了横坐标相同的特殊情况。

这种处理方式基于直线的斜率特性。斜率的绝对值表示直线倾斜的程度。当斜率的绝对值大于1时，这意味着直线在y轴方向上的变化比x轴方向上的变化更快。因此，在每个单位x的变化中，直线在y方向上变化超过1单位。在这种情况下，直线更有可能与正方形的垂直边界（即上下边界）相交，而不是水平边界（即左右边界）。因此，当斜率的绝对值大于1时，计算交点主要集中于垂直边界，这是为了确保正确地捕捉到直线与正方形边界的交点。

在使用浮点数计算斜率和截距时，确实可能会出现精度误差。为了尽可能减少这种误差，可以采取以下几种方法：1. 使用高精度的浮点数类型（如Python中的`decimal.Decimal`），这可以提供比标准浮点数更精确的计算。2. 在计算过程中尽量避免除法操作，因为除法是引入浮点误差的常见源头。例如，可以直接使用两点式（点斜式）来定义直线，而不是先计算斜率再计算截距。3. 在最终结果输出前，对计算得到的浮点数进行适当的四舍五入，以减少对最终结果的影响。4. 使用图形学中的算法来直接从几何角度计算交点，这样可以绕开对斜率和截距的直接计算，从而减少误差。