文章目錄
1. 題目
在一個(gè)二維的花園中，有一些用 (x, y) 坐標(biāo)表示的樹。
由于安裝費(fèi)用十分昂貴，你的任務(wù)是先用最短的繩子圍起所有的樹。
只有當(dāng)所有的樹都被繩子包圍時(shí)，花園才能圍好柵欄。
你需要找到正好位于柵欄邊界上的樹的坐標(biāo)。
示例 1:
輸入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
輸出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
解釋:
示例 2:
輸入: [[1,2],[2,2],[4,2]]
輸出: [[1,2],[2,2],[4,2]]
解釋:
即使樹都在一條直線上，你也需要先用繩子包圍它們。
注意:
所有的樹應(yīng)當(dāng)被圍在一起。你不能剪斷繩子來包圍樹或者把樹分成一組以上。
輸入的整數(shù)在 0 到 100 之間。
花園至少有一棵樹。
所有樹的坐標(biāo)都是不同的。
輸入的點(diǎn)沒有順序。輸出順序也沒有要求。
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/erect-the-fence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
LintCode 題目地址：https://www.lintcode.com/problem/erect-the-fence/description
2. 解題
- 將所有的點(diǎn)按 x，y 排序
- 先將前面兩個(gè)點(diǎn)加入答案，正序檢查當(dāng)前點(diǎn)跟答案里最后兩個(gè)點(diǎn)組成的向量的叉積指向是否滿足凸包要求，不滿足，則將答案里最后一個(gè)點(diǎn)彈出，滿足，則將點(diǎn)壓入答案。得到下邊界
- 然后逆序檢查，得到上邊界，然后去重
下圖考慮的是下邊界，正序遍歷的情況
struct cmp
{bool operator()(const Point a
, const Point b
) const{return a
.x
<b
.x
|| (a
.x
==b
.x
&& a
.y
<b
.y
);}
};
class Solution {
public:vector
<Point
> outerTrees(vector
<Point
> &points
) {sort(points
.begin(), points
.end(),[&](auto &a
, auto &b
){return a
.x
< b
.x
|| (a
.x
== b
.x
&& a
.y
< b
.y
);});vector
<Point
> ans
;for(int i
= 0; i
< points
.size(); ++i
){while(ans
.size()>=2 && dot(ans
[ans
.size()-2], ans
[ans
.size()-1],points
[i
]) < 0)ans
.pop_back();ans
.push_back(points
[i
]);}for(int i
= points
.size()-1; i
>= 0; --i
){while(ans
.size()>=2 && dot(ans
[ans
.size()-2], ans
[ans
.size()-1],points
[i
]) < 0)ans
.pop_back();ans
.push_back(points
[i
]);}set
<Point
, cmp
> set(ans
.begin(), ans
.end());vector
<Point
> res(set
.begin(), set
.end());return res
;}int dot(Point
& a
, Point
& b
, Point
& c
){int x1
= b
.x
-a
.x
;int y1
= b
.y
-a
.y
;int x2
= c
.x
-b
.x
;int y2
= c
.y
-b
.y
;return x1
*y2
-x2
*y1
;}
};
class Solution {
public:vector
<vector
<int>> outerTrees(vector
<vector
<int>>& points
) {sort(points
.begin(), points
.end());vector
<vector
<int>> ans
;for(int i
= 0; i
< points
.size(); ++i
){while(ans
.size()>=2 && dot(ans
[ans
.size()-2], ans
[ans
.size()-1],points
[i
]) < 0)ans
.pop_back();ans
.push_back(points
[i
]);}for(int i
= points
.size()-1; i
>= 0; --i
){while(ans
.size()>=2 && dot(ans
[ans
.size()-2], ans
[ans
.size()-1],points
[i
]) < 0)ans
.pop_back();ans
.push_back(points
[i
]);}set
<vector
<int>> set(ans
.begin(), ans
.end());vector
<vector
<int>> res(set
.begin(), set
.end());return res
;}int dot(vector
<int>& a
, vector
<int>& b
, vector
<int>& c
){int x1
= b
[0]-a
[0];int y1
= b
[1]-a
[1];int x2
= c
[0]-b
[0];int y2
= c
[1]-b
[1];return x1
*y2
-x2
*y1
;}
};
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！
總結(jié)
以上是生活随笔為你收集整理的LeetCode 587. 安装栅栏 / LintCode 1152. 安装栅栏（凸包检测：排序+叉积正负判断+正反扫描+去重）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
