程序员面试金典 - 面试题 16.13. 平分正方形（数学）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 16.13. 平分正方形（数学），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2196字，纯文字阅读大概需要4分钟。
内容图文
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
内容总结
以上是互联网集市为您收集整理的程序员面试金典 - 面试题 16.13. 平分正方形（数学）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 16.13. 平分正方形（数学）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。