生活随笔
收集整理的這篇文章主要介紹了
LeetCode 963. 最小面积矩形 II
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 題目
給定在 xy 平面上的一組點，確定由這些點組成的任何矩形的最小面積，其中矩形的邊不一定平行于 x 軸和 y 軸。
如果沒有任何矩形，就返回 0。
示例 1：
輸入：
[[1,2],[2,1],[1,0],[0,1]]
輸出：
2.00000
解釋：最小面積的矩形出現在
[1,2],[2,1],[1,0],[0,1] 處，面積為
2。示例
2：
輸入：
[[0,1],[2,1],[1,1],[1,0],[2,0]]
輸出：
1.00000
解釋：最小面積的矩形出現在
[1,0],[1,1],[2,1],[2,0] 處，面積為
1。示例
3：
輸入：
[[0,3],[1,2],[3,1],[1,3],[2,1]]
輸出：
0
解釋：沒法從這些點中組成任何矩形。示例
4：
輸入：
[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
輸出：
2.00000
解釋：最小面積的矩形出現在
[2,1],[2,3],[3,3],[3,1] 處，面積為
2。提示：
1 <= points
.length
<= 50
0 <= points
[i
][0] <= 40000
0 <= points
[i
][1] <= 40000
所有的點都是不同的。
與真實值誤差不超過
10^-5 的答案將視為正確結果。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-area-rectangle-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
class point{
public
:int x
, y
;point
(int x
, int y
){this
->x
= x
;this
->y
= y
;}bool operator
<(point a
) const
{return (x
==a
.x
&& y
< a
.y
) || (x
< a
.x
);}
};
class Solution {
public
:double minAreaFreeRect
(vector
<vector
<int>>& points
) {map<int,map<point
,vector
<point
>>> m
;// square
len, midpoint
, point
int n
= points
.size
(), x1
,x2
,y1
,y2
,x3
,y3
,d
;int midx
, midy
;for(int i
= 0; i
< n
; ++i
){for(int j
= i
+1; j
< n
; ++j
){x1
= points
[i
][0];y1
= points
[i
][1];x2
= points
[j
][0];y2
= points
[j
][1];midx
= (x1
+x2
);//不除以
2midy
= (y1
+y2
);d
= dis
(x1
,y1
,x2
,y2
);m
[d
][point
(midx
, midy
)].push_back
(point
(x1
,y1
));}}double area
= INT_MAX
;int dx1
,dy1
,dx2
,dy2
;for(auto it
= m
.begin
(); it
!= m
.end
(); ++it
){for(auto it1
= it
->second
.begin
(); it1
!= it
->second
.end
(); ++it1
){midx
= it1
->first
.x
;midy
= it1
->first
.y
;for(int i
= 0; i
< it1
->second
.size
(); ++i
){x1
= it1
->second
[i
].x
;y1
= it1
->second
[i
].y
;x2
= midx
-x1
;y2
= midy
-y1
;for(int j
= i
+1; j
< it1
->second
.size
(); ++j
){x3
= it1
->second
[j
].x
;y3
= it1
->second
[j
].y
;dx1
= x1
-x3
, dy1
= y1
-y3
;dx2
= x2
-x3
, dy2
= y2
-y3
;if(dx1
*dx2
+dy1
*dy2
==0){area
= min(area
, sqrt
(dx1
*dx1
+dy1
*dy1
)*sqrt
(dx2
*dx2
+dy2
*dy2
));}}}}}return area
== INT_MAX ?
0 : area
;}int dis
(int x1
, int y1
, int x2
, int y2
){return (x1
-x2
)*(x1
-x2
)+(y1
-y2
)*(y1
-y2
);}
};
52 ms 21.6 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的LeetCode 963. 最小面积矩形 II的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
