原文链接: https://leetcode-cn.com/problems/bisect-squares-lcci

英文原文

Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

Each square consists of three values, the coordinate of bottom left corner [X,Y] = [square[0],square[1]], and the side length of the square square[2]. The line will intersect to the two squares in four points. Return the coordinates of two intersection points [X1,Y1] and [X2,Y2] that the forming segment covers the other two intersection points in format of {X1,Y1,X2,Y2}. If X1 != X2, there should be X1 < X2, otherwise there should be Y1 <= Y2.

If there are more than one line that can cut these two squares in half, return the one that has biggest slope (slope of a line parallel to the y-axis is considered as infinity).

Example:

Input: 
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
Output: {-1,0,2,0}
Explanation: y = 0 is the line that can cut these two squares in half.

Note:

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

中文题目

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

通过代码

高赞题解

为了平分两个正方形，直线一定经过这两个正方形的中心(cx1, cy1)和(cx2, cy2)，可以用两点式

(x - cx1) / (cx2 - cx1) = (y - cy1) / (cy2 - cy1) 

推导出直线公式。

需要处理两种特殊情况，cx1 == cx2和cy1 == cy2:
当cx1 == cx2时，直线与y轴平行；
当cy1 == cy2时，直线与x轴平行。

一条直线平分正方形时，会穿过这个正方形的两条边，交点的x坐标或y坐标会与正方形的一个顶点的x坐标或y坐标相等。因此，将正方形的顶点代入直线方程，得到每个正方形有四个候选点，只选择在正方形内的候选点。

最后，对顶点集res进行排序，所求顶点为排序后的res数组的第一个顶点和最后一个顶点。

class Solution {
public:
    vector<double> cutSquares(vector<int>& square1, vector<int>& square2) {
        // 计算两个正方形中心(cx1, cy1), (cx2, cy2)
        double cx1 = square1[0] + ((double)square1[2]) / 2;
        double cy1 = square1[1] + ((double)square1[2]) / 2;

        double cx2 = square2[0] + ((double)square2[2]) / 2;
        double cy2 = square2[1] + ((double)square2[2]) / 2;

        vector<pair<double, double> > res; // 候选顶点集
        // 处理特殊情况cx1 == cx2和cy1 == cy2
        if (cx1 == cx2) {
            res.push_back({cx1, square1[1]});
            res.push_back({cx1, square2[1]});
            res.push_back({cx1, square1[1]+square1[2]});
            res.push_back({cx1, square2[1]+square2[2]});
        } else if (cy1 == cy2) {
            res.push_back({square1[0], cy1});
            res.push_back({square2[0], cy1});
            res.push_back({square1[0]+square1[2], cy1});
            res.push_back({square2[0]+square2[2], cy1});
        } else {
            // 直线方程f(y)
            auto fy = [=](double y) -> double {
                const double k = (cx2 - cx1) / (cy2 - cy1);
                return k * (y - cy1) + cx1;
            };
            // 直线方程f(x)
            auto fx = [=](double x) -> double {
                const double k = (cy2 - cy1) / (cx2 - cx1);
                return k * (x - cx1) + cy1;
            };
            for (auto &sq : {square1, square2}) {
                for (auto &p : vector<pair<double, double> >{
                    {fy(sq[1]), sq[1]},
                    {fy(sq[1]+sq[2]), sq[1]+sq[2]},
                    {sq[0], fx(sq[0])},
                    {sq[0]+sq[2], fx(sq[0]+sq[2])}})
                {
                    // 判断候选顶点是否在正方形中
                    if (p.first >= sq[0] && p.first <= sq[0] + sq[2]) {
                        if (p.second >= sq[1] && p.second <= sq[1] + sq[2]) {
                            res.push_back(p);
                        }
                    }
                }
            }
        }
        // 对顶点集排序
        sort(res.begin(), res.end());
        // 所求顶点为排序后的`res`数组的第一个顶点和最后一个顶点。
        return {
            res.front().first,
            res.front().second,
            res.back().first,
            res.back().second,
        };
    }
};

统计信息

通过次数	提交次数	AC比率
2113	4948	42.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言