邢台邯郸做网站,上海网站推广优化,北京网站建设公司华网,新闻发稿平台有哪些1. 题目
给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。 假设正方形顶边和底边与 x 轴平行。
每个正方形的数据square包含3个数值#xff0c;正方形的左下顶点坐标[X,Y] [square[0],square[1]]#xff0c;以及正方形的边长square[2]。 所求直…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:vectordouble cutSquares(vectorint square1, vectorint 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(cx1cx2)//斜率无穷大return {cx1,cy1-r1,cx1,max(cy1r1,cy2r2)};else//斜率存在,分两种情况与上下边相交左右边相交{double k (cy1-cy2)/(cx1-cx2);double b cy1-k*cx1;vectorvectordouble points;if(abs(k)1)//交点在上下边{points.push_back({(cy1r1-b)/k, cy1r1});points.push_back({(cy1-r1-b)/k, cy1-r1});points.push_back({(cy2r2-b)/k, cy2r2});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({cx1r1, k*(cx1r1)b});points.push_back({cx1-r1, k*(cx1-r1)b});points.push_back({cx2r2, k*(cx2r2)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
