Geometry
Array
Math
Description
You are given an array trees
where trees[i] = [xi , yi ]
represents the location of a tree in the garden.
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 .
Return the coordinates of trees that are exactly located on the fence perimeter . You may return the answer in any order .
Example 1:
Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.
Example 2:
Input: trees = [[1,2],[2,2],[4,2]]
Output: [[4,2],[2,2],[1,2]]
Explanation: The fence forms a line that passes through all the trees.
Constraints:
1 <= trees.length <= 3000
trees[i].length == 2
0 <= xi , yi <= 100
All the given positions are unique .
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution :
def outerTrees ( self , trees : List [ List [ int ]]) -> List [ List [ int ]]:
def cross ( i , j , k ):
a , b , c = trees [ i ], trees [ j ], trees [ k ]
return ( b [ 0 ] - a [ 0 ]) * ( c [ 1 ] - b [ 1 ]) - ( b [ 1 ] - a [ 1 ]) * ( c [ 0 ] - b [ 0 ])
n = len ( trees )
if n < 4 :
return trees
trees . sort ()
vis = [ False ] * n
stk = [ 0 ]
for i in range ( 1 , n ):
while len ( stk ) > 1 and cross ( stk [ - 2 ], stk [ - 1 ], i ) < 0 :
vis [ stk . pop ()] = False
vis [ i ] = True
stk . append ( i )
m = len ( stk )
for i in range ( n - 2 , - 1 , - 1 ):
if vis [ i ]:
continue
while len ( stk ) > m and cross ( stk [ - 2 ], stk [ - 1 ], i ) < 0 :
stk . pop ()
stk . append ( i )
stk . pop ()
return [ trees [ i ] for i in stk ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution {
public int [][] outerTrees ( int [][] trees ) {
int n = trees . length ;
if ( n < 4 ) {
return trees ;
}
Arrays . sort ( trees , ( a , b ) -> { return a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ] ; });
boolean [] vis = new boolean [ n ] ;
int [] stk = new int [ n + 10 ] ;
int cnt = 1 ;
for ( int i = 1 ; i < n ; ++ i ) {
while ( cnt > 1 && cross ( trees [ stk [ cnt - 1 ]] , trees [ stk [ cnt - 2 ]] , trees [ i ] ) < 0 ) {
vis [ stk [-- cnt ]] = false ;
}
vis [ i ] = true ;
stk [ cnt ++] = i ;
}
int m = cnt ;
for ( int i = n - 1 ; i >= 0 ; -- i ) {
if ( vis [ i ] ) {
continue ;
}
while ( cnt > m && cross ( trees [ stk [ cnt - 1 ]] , trees [ stk [ cnt - 2 ]] , trees [ i ] ) < 0 ) {
-- cnt ;
}
stk [ cnt ++] = i ;
}
int [][] ans = new int [ cnt - 1 ][ 2 ] ;
for ( int i = 0 ; i < ans . length ; ++ i ) {
ans [ i ] = trees [ stk [ i ]] ;
}
return ans ;
}
private int cross ( int [] a , int [] b , int [] c ) {
return ( b [ 0 ] - a [ 0 ] ) * ( c [ 1 ] - b [ 1 ] ) - ( b [ 1 ] - a [ 1 ] ) * ( c [ 0 ] - b [ 0 ] );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
public :
vector < vector < int >> outerTrees ( vector < vector < int >>& trees ) {
int n = trees . size ();
if ( n < 4 ) return trees ;
sort ( trees . begin (), trees . end ());
vector < int > vis ( n );
vector < int > stk ( n + 10 );
int cnt = 1 ;
for ( int i = 1 ; i < n ; ++ i ) {
while ( cnt > 1 && cross ( trees [ stk [ cnt - 1 ]], trees [ stk [ cnt - 2 ]], trees [ i ]) < 0 ) vis [ stk [ -- cnt ]] = false ;
vis [ i ] = true ;
stk [ cnt ++ ] = i ;
}
int m = cnt ;
for ( int i = n - 1 ; i >= 0 ; -- i ) {
if ( vis [ i ]) continue ;
while ( cnt > m && cross ( trees [ stk [ cnt - 1 ]], trees [ stk [ cnt - 2 ]], trees [ i ]) < 0 ) -- cnt ;
stk [ cnt ++ ] = i ;
}
vector < vector < int >> ans ;
for ( int i = 0 ; i < cnt - 1 ; ++ i ) ans . push_back ( trees [ stk [ i ]]);
return ans ;
}
int cross ( vector < int >& a , vector < int >& b , vector < int >& c ) {
return ( b [ 0 ] - a [ 0 ]) * ( c [ 1 ] - b [ 1 ]) - ( b [ 1 ] - a [ 1 ]) * ( c [ 0 ] - b [ 0 ]);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 func outerTrees ( trees [][] int ) [][] int {
n := len ( trees )
if n < 4 {
return trees
}
sort . Slice ( trees , func ( i , j int ) bool {
if trees [ i ][ 0 ] == trees [ j ][ 0 ] {
return trees [ i ][ 1 ] < trees [ j ][ 1 ]
}
return trees [ i ][ 0 ] < trees [ j ][ 0 ]
})
cross := func ( i , j , k int ) int {
a , b , c := trees [ i ], trees [ j ], trees [ k ]
return ( b [ 0 ] - a [ 0 ]) * ( c [ 1 ] - b [ 1 ]) - ( b [ 1 ] - a [ 1 ]) * ( c [ 0 ] - b [ 0 ])
}
vis := make ([] bool , n )
stk := [] int { 0 }
for i := 1 ; i < n ; i ++ {
for len ( stk ) > 1 && cross ( stk [ len ( stk ) - 1 ], stk [ len ( stk ) - 2 ], i ) < 0 {
vis [ stk [ len ( stk ) - 1 ]] = false
stk = stk [: len ( stk ) - 1 ]
}
vis [ i ] = true
stk = append ( stk , i )
}
m := len ( stk )
for i := n - 1 ; i >= 0 ; i -- {
if vis [ i ] {
continue
}
for len ( stk ) > m && cross ( stk [ len ( stk ) - 1 ], stk [ len ( stk ) - 2 ], i ) < 0 {
stk = stk [: len ( stk ) - 1 ]
}
stk = append ( stk , i )
}
var ans [][] int
for i := 0 ; i < len ( stk ) - 1 ; i ++ {
ans = append ( ans , trees [ stk [ i ]])
}
return ans
}
GitHub