面试题 16.13. 平分正方形

参考面试题 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轴平行的直线视为斜率无穷大）。square.length == 3 , square[2] > 0

输入：square1 = {-1, -1, 2},square2 = {0, -1, 2}
输出： {-1,0,2,0}
解释： 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]

解题思路

• 数学：要想平分正方形,需要经过正方形中心点,要平分两个正方形,则直线需经过两个正方形的中心点即可。根据中心点计算直线的斜率后分类讨论:
  1. 是否与x轴平行.
  2. 斜率绝对值是否小于1即倾斜45度以内与正方形的竖边相交,否则与横边相交,同时判断斜率是否为0.

数学

class Solution {
    public double[] cutSquares(int[] square1, int[] square2) {
        //经过正方形中心点即可平分正方形 平分两个即经过两个中心点
        double pos1x = square1[0]+square1[2]/2.0;
        double pos1y = square1[1]+square1[2]/2.0;
        double pos2x = square2[0]+square2[2]/2.0;
        double pos2y = square2[1]+square2[2]/2.0;
        //根据直线方程 斜率 = (y2-y1)/(x2-x1)
        if(pos2x == pos1x) { //y轴平行 x = pos1x
            return new double[]{pos1x,Math.min(square1[1],square2[1])
                ,pos1x,Math.max(square1[1]+square1[2],square2[1]+square2[2])};
        }else { //y = kx + b
            double k = (pos2y-pos1y)/(pos2x-pos1x),b = pos1y-k*pos1x;
            //根据斜率是否大于45度即|k|>1来区分交点落在正方向横边还是竖边
            if(Math.abs(k) < 1) { //计算y
                double x1 = Math.min(square1[0],square2[0]);
                double x2 = Math.max(square1[0]+square1[2],square2[0]+square2[2]);
                return new double[]{x1,k*x1+b,x2,k*x2+b};
            }else {//计算x
                double y1 = Math.min(square1[1],square2[1]);
                double y2 = Math.max(square1[1]+square1[2],square2[1]+square2[2]);
                if(k == 0) { //x轴平行 y = pos1y
                    return new double[]{Math.min(square1[0],square2[0]),pos1y,
                        Math.max(square1[0]+square1[2],square2[0]+square2[2]),pos1y};
                }
                //判断较小的x
                double x1 = (y1-b)/k, x2 = (y2-b)/k;
                if(x1 < x2) {
                    return new double[]{x1,y1,x2,y2};
                }else {
                    return new double[]{x2,y2,x1,y1};
                }
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(1)，计算花费固定时间。
• 空间复杂度：O(1)。