題目
今天的力扣（LCUS）每日挑戰是 587. 安裝柵欄．
在一個二維的花園中，有一些用
座標表示的樹．由於安裝費用十分昂貴，你的任務是先用最短的繩子圍起所有的樹．只有當所有的樹都被繩子包圍時，花園才能圍好柵欄．你需要找到正好位於柵欄邊界上的樹的座標．
知識點
其實質是求若干點組成的二維 凸包（convex hull）．常用的求法有 Graham 掃描法（Graham's scan）和 Andrew 演算法，本文提供了一個由 Rust 實現的 Graham 掃描法．
思路
演算法的步驟如下：
- 若點個數少於 3 個，則直接返回輸入．否則按如下方法求解．
- 首先，找出縱座標最小的點．若有多個，則選橫座標最小的點．以該點建立極座標系．
- 此時，將所有的點按照極角的大小升序排列，若有極角相同的，則再按該點到極點距離升序排列．
- 然後維護一個棧．先將排列好的點的前兩個入棧，然後對於其後的每一個點
- 處理完所有的點後，需要再找出不在棧中但在棧的最後一個點與棧的第一個點構成的線段上的點．
示例
輸入資料
[[3,0],[4,0],[5,0],[6,1],[7,2],[7,3],[7,4],[6,5],[5,5],[4,5],[3,5],[2,5],[1,4],[1,3],[1,2],[2,1],[4,2],[0,3]]- - * * * * * -
- * - - - - - *
* * - - - - - *
- * - - * - - *
- - * - - - * -
- - - * * * - -
預期結果
[[4,5],[2,5],[6,1],[3,5],[2,1],[1,4],[1,2],[7,4],[7,3],[7,2],[3,0],[0,3],[5,0],[5,5],[4,0],[6,5]]- - * * * * * -
- * - - - - - *
* - - - - - - *
- * - - - - - *
- - * - - - * -
- - - * - * - -
錯誤結果
若沒有第 5 步，則缺少兩點
[[7,3],[5,0],[7,4],[4,5],[1,4],[4,0],[5,5],[6,1],[3,0],[6,5],[2,5],[7,2],[0,3],[3,5]]- - * * * * * -
- * - - - - - *
* - - - - - - *
- - - - - - - *
- - - - - - * -
- - - * * * - -
計算
需要用到一些向量的性質．
判斷逆時針
兩向量叉積為正，則
判斷點線上段上
記線段為
程式碼
use std::{cmp::Ordering::*, collections::HashSet};
#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)]
struct Tree(i32, i32);
impl Solution {
#[inline]
fn cross_product(x_1: i32, y_1: i32, x_2: i32, y_2: i32) -> i32 {
x_1 * y_2 - x_2 * y_1
}
pub fn outer_trees(trees: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
if trees.len() < 3 {
return trees;
}
let mut init = (114514, 114514);
trees.iter().for_each(|t| match t[1].cmp(&init.1) {
Less => {
init = (t[0], t[1]);
}
Equal => {
init.0 = init.0.min(t[0]);
}
_ => {}
});
// println!("左下角的點是 {:?}", init);
let mut trees: Vec<Tree> = trees
.into_iter()
.map(|t| Tree(t[0] - init.0, t[1] - init.1))
// 這裡以左下角的點為 (0, 0)
.collect();
trees.sort_by(
|a, b| match { 0.cmp(&Self::cross_product(a.0, a.1, b.0, b.1)) } {
Equal => (a.0.pow(2) + a.1.pow(2)).cmp(&(b.0.pow(2) + b.1.pow(2))),
res => res,
},
);
let mut stack = Vec::new();
stack.push(trees[0]);
stack.push(trees[1]);
for t in trees.iter().skip(2) {
while {
let length = stack.len();
length > 1 && {
let (a, b) = (stack[stack.len() - 2], stack[stack.len() - 1]);
let x_1 = t.0 - a.0;
let y_1 = t.1 - a.1;
let x_2 = b.0 - a.0;
let y_2 = b.1 - a.1;
Self::cross_product(x_1, y_1, x_2, y_2) > 0
}
} {
stack.pop().unwrap();
}
stack.push(t.clone());
}
let mut trees: HashSet<_> = trees.into_iter().collect();
for x in &stack {
trees.remove(x);
}
let Tree(p1x, p1y) = stack[stack.len() - 1];
let Tree(p2x, p2y) = stack[0];
let extra: Vec<Tree> = trees // 棧中最後一個點與棧中第一個點構成的線段上的點
.into_iter()
.filter_map(|a| {
let Tree(p_x, p_y) = a;
let vec1 = (p_x - p1x, p_y - p1y);
let vec2 = (p_x - p2x, p_y - p2y);
if (vec1.0 * vec2.0 + vec1.1 * vec2.1).pow(2)
== (vec1.0.pow(2) + vec1.1.pow(2)) * (vec2.0.pow(2) + vec2.1.pow(2))
{
Some(a)
} else {
None
}
})
.collect();
stack
.into_iter()
.chain(extra.into_iter())
.map(|x| vec![x.0 + init.0, x.1 + init.1])
.collect()
}
}
// 以下是測試部分
struct Solution;
fn main() {
let res: HashSet<Vec<i32>> = HashSet::from_iter(
Solution::outer_trees(vec![vec![1, 1], vec![2, 2],
vec![2, 0], vec![2, 4], vec![3, 3], vec![4, 2]]).into_iter(),
);
assert_eq!(
res,
HashSet::from_iter(
vec![vec![1, 1], vec![2, 0], vec![4, 2],
vec![3, 3], vec![2, 4]].into_iter()
)
);
let res: HashSet<Vec<i32>> = HashSet::from_iter(Solution::outer_trees(vec![
vec![3, 0], vec![4, 0], vec![5, 0], vec![6, 1], vec![7, 2], vec![7, 3],
vec![7, 4], vec![6, 5], vec![5, 5], vec![4, 5], vec![3, 5], vec![2, 5],
vec![1, 4], vec![1, 3], vec![1, 2], vec![2, 1], vec![4, 2], vec![0, 3]
]));
assert_eq!(
res, HashSet::from_iter(
vec![vec![4, 5], vec![2, 5], vec![6, 1], vec![3, 5], vec![2, 1],
vec![1, 4], vec![1, 2], vec![7, 4], vec![7, 3], vec![7, 2], vec![3, 0],
vec![0, 3], vec![5, 0], vec![5, 5], vec![4, 0], vec![6, 5]].into_iter()
)
);
}以上．
版权许可
- 本作品 采用 知识共享 署名—非商业性使用 4.0 国际许可协议（CC BY-NC 4.0 International）许可，阁下可自由地共享（复制、发行） 和演绎（修改、转换或二次创作） 这一作品，唯须遵守许可协议条款。
评论