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