1. 题目
给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。
假设正方形顶边和底边与 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 复制
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bisect-squares-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 过两个正方形中心的直线
- 分成斜率无穷大（垂直于x轴）、斜率绝对值>=1、< 1 考虑
- 交点在上下边，还是在左右边
class Solution {
public:
vector<double> cutSquares(vector<int>& square1, vector<int>& square2) {
if(square1[1] > square2[1])
swap(square1,square2);//第一个的左下角y坐标更小
double cx1, cy1, cx2, cy2, r1, r2;
r1 = square1[2]/2.0;
r2 = square2[2]/2.0;
cx1 = square1[0]+r1;//中心坐标
cy1 = square1[1]+r1;
cx2 = square2[0]+r2;
cy2 = square2[1]+r2;
if(cx1==cx2)//斜率无穷大
return {cx1,cy1-r1,cx1,max(cy1+r1,cy2+r2)};
else//斜率存在,分两种情况，与上下边相交，左右边相交
{
double k = (cy1-cy2)/(cx1-cx2);
double b = cy1-k*cx1;
vector<vector<double>> points;
if(abs(k)>=1)//交点在上下边
{
points.push_back({(cy1+r1-b)/k, cy1+r1});
points.push_back({(cy1-r1-b)/k, cy1-r1});
points.push_back({(cy2+r2-b)/k, cy2+r2});
points.push_back({(cy2-r2-b)/k, cy2-r2});
sort(points.begin(),points.end());
return {points.front()[0],points.front()[1],points.back()[0],points.back()[1]};
}
else//交点在左右边
{
points.push_back({cx1+r1, k*(cx1+r1)+b});
points.push_back({cx1-r1, k*(cx1-r1)+b});
points.push_back({cx2+r2, k*(cx2+r2)+b});
points.push_back({cx2-r2, k*(cx2-r2)+b});
sort(points.begin(),points.end());
return {points.front()[0],points.front()[1],points.back()[0],points.back()[1]};
}
}
}
}; 复制
4 ms 8.6 MB