587. Erect the Fence

Description

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 theminimum lengthof 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]]

Example 2:

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

Discussion

Method 1 (Wrong)

assume one coordinator can only contain at most two points (x direction, y direction)

method 2

sort first, then find rules.