class Solution {
public:
vector<double> cutSquares(vector<int>& square1, vector<int>& square2) {
}
};
面试题 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轴平行的直线视为斜率无穷大）。
示例：
输入：
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
输出： {-1,0,2,0}
解释： 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]
提示：
square.length == 3square[2] > 0原站题解
python3 解法, 执行用时: 28 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-30 11:03:21
class Solution:
def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:
get_x = lambda y: (y - b) / k
get_y = lambda x: k * x + b
(x1, y1, l1), (x2, y2, l2) = square1, square2
c1 = (x1 + l1 / 2, y1 + l1 / 2)
c2 = (x2 + l2 / 2, y2 + l2 / 2)
dy, dx = c2[1] - c1[1], c2[0] - c1[0]
points = []
if dx == 0:
points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]
else:
k = dy / dx
b = c1[1] - c1[0] * k
if -1 <= k <= 1:
points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)),
(x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]
else:
points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),
(get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]
points = sorted(points)
return [*points[0], *points[-1]]
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-11-30 11:02:54
class Solution:
def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:
getCenter = lambda x,y,r: [x+r/2,y+r/2]
getAbc = lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1] #中心重合
crossY = lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)
crossX = lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)
a, b, c = getAbc(*getCenter(*square1),*getCenter(*square2))
(x1,y1,r1),(x2,y2,r2) = square1, square2
left,right,bottom,top = min(x1,x2), max(x1+r1,x2+r2) , min(y1,y2), max(y1+r1,y2+r2)
res = [pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]
return [v for x,y in sorted(res) for v in [x,y]]
java 解法, 执行用时: 0 ms, 内存消耗: 40.3 MB, 提交时间: 2022-11-30 10:57:14
class Solution {
public double[] cutSquares(int[] square1, int[] square2) {
//第一个正方形的中心点，x,y坐标及正方形边长
double x1 = square1[0] + square1[2]/2.0;
double y1 = square1[1] + square1[2]/2.0;
int d1 = square1[2];
//第二个正方形的中心点，x,y坐标及正方形边长
double x2 = square2[0] + square2[2]/2.0;
double y2 = square2[1] + square2[2]/2.0;
int d2 = square2[2];
//结果集
double[] res = new double[4];
//两个中心坐标在同一条x轴上，此时两条直线的斜率都是无穷大
if(x1 == x2){
res[0] = x1;
res[1] = Math.min(square1[1], square2[1]);
res[2] = x1;
res[3] = Math.max(square1[1] + d1, square2[1] + d2);
}else{
//斜率存在，则计算斜率和系数，y = kx + b;
double k = (y1 - y2)/(x1 - x2);//斜率计算公式
double b = y1 - k*x1;
//斜率绝对值大于1，说明与正方形的上边和下边相交
if(Math.abs(k) > 1){
//先计算底边，也就是两个正方形左下坐标y的最小值
res[1] = Math.min(square1[1],square2[1]);
res[0] = (res[1] - b)/k;
//再计算顶边，也就是两个正方形左下坐标y+边长的最大值
res[3] = Math.max(square1[1] + d1,square2[1] + d2);
res[2] = (res[3] - b)/k;
}else{
//斜率绝对值小于等于1，说明与正方形的左边和右边相交，同理
res[0] = Math.min(square1[0],square2[0]);
res[1] = res[0]*k + b;
res[2] = Math.max(square1[0] + d1,square2[0] + d2);
res[3] = res[2]*k + b;
}
}
//题目要求x1 < x2,如果结果不满足，我们交换两个点的坐标即可
if(res[0] > res[2]){
swap(res, 0 ,2);
swap(res, 1, 3);
}
return res;
}
public void swap(double[] res, int x, int y){
double temp = res[x];
res[x] = res[y];
res[y] = temp;
}
}