[Swift]LeetCode587.安装栅栏|ErecttheFence

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10440054.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

Example 1:

Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation:

Example 2:

Input: [[1,2],[2,2],[4,2]]
Output: [[1,2],[2,2],[4,2]]
Explanation:

Even you only have trees in a line, you need to use rope to enclose them.

Note:

All trees should be enclosed together. You cannot cut the rope to enclose trees that will separate them in more than one group.
All input integers will range from 0 to 100.
The garden has at least one tree.
All coordinates are distinct.
Input points have NO order. No order required for output.

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

示例 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]]
解释:

即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
输入的整数在 0 到 100 之间。
花园至少有一棵树。
所有树的坐标都是不同的。
输入的点没有顺序。输出顺序也没有要求。

Runtime: 292 ms

Memory Usage: 20.1 MB

 1 /**
 2  * Definition for a point.
 3  * public class Point {
 4  *   public var x: Int
 5  *   public var y: Int
 6  *   public init(_ x: Int, _ y: Int) {
 7  *     self.x = x
 8  *     self.y = y
 9  *   }
10  * }
11  */
12 class Solution {    
13     func outerTrees(_ points: [Point]) -> [Point] {
14         var res:[Point] = [Point]()
15         var first:Point = points[0]
16         var firstIdx:Int = 0
17         var n:Int = points.count
18         for i in 1..<n
19         {
20             if points[i].x < first.x
21             {
22                 first = points[i]
23                 firstIdx = i
24             }
25         }
26         res.append(first)
27         var cur:Point = first
28         var curIdx:Int = firstIdx
29         while(true)
30         {
31             var next:Point = points[0]
32             var nextIdx:Int = 0
33             for i in 1..<n
34             {
35                 if i == curIdx {continue}
36                 var cross:Int = crossProduct(cur, points[i], next)
37                 if nextIdx == curIdx || cross > 0 || (cross == 0 && dist(points[i], cur) > dist(next, cur))
38                 {
39                     next = points[i]
40                     nextIdx = i
41                 }
42             }
43             for i in 0..<n
44             {
45                 if i == curIdx {continue}
46                 var cross:Int = crossProduct(cur, points[i], next)
47                 if cross == 0
48                 {
49                     if check(&res, points[i])
50                     {
51                         res.append(points[i])
52                     }
53                 }
54             }
55             cur = next
56             curIdx = nextIdx
57             if curIdx == firstIdx {break}
58         }
59         return res
60     }
61     
62     func crossProduct(_ A:Point,_ B:Point,_ C:Point) -> Int
63     {
64         var BAx:Int = A.x - B.x;
65         var BAy:Int = A.y - B.y;
66         var BCx:Int = C.x - B.x;
67         var BCy:Int = C.y - B.y;
68         return BAx * BCy - BAy * BCx;
69     }
70     
71     func dist(_ A:Point,_ B:Point) -> Int
72     {
73         return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)
74     }
75     
76     func check(_ res:inout [Point],_ p:Point) -> Bool
77     {
78         for r in res
79         {
80             if r.x == p.x && r.y == p.y {return false}
81         }
82         return true
83     }
84 }