<p>You are given an array <code>trees</code> where <code>trees[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents the location of a tree in the garden.</p>

<p>Fence the entire garden using the minimum length of rope, as it is expensive. The garden is well-fenced only if <strong>all the trees are enclosed</strong>.</p>

<p>Return <em>the coordinates of trees that are exactly located on the fence perimeter</em>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/24/erect2-plane.jpg" style="width: 400px; height: 393px;" />
<pre>
<strong>Input:</strong> trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
<strong>Output:</strong> [[1,1],[2,0],[4,2],[3,3],[2,4]]
<strong>Explanation:</strong> All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/24/erect1-plane.jpg" style="width: 400px; height: 393px;" />
<pre>
<strong>Input:</strong> trees = [[1,2],[2,2],[4,2]]
<strong>Output:</strong> [[4,2],[2,2],[1,2]]
<strong>Explanation:</strong> The fence forms a line that passes through all the trees.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= trees.length &lt;= 3000</code></li>
	<li><code>trees[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>
	<li>All the given positions are <strong>unique</strong>.</li>
</ul>

class Solution {
public:

    int n,x,y,ix,d,dm,p,xm;
    float m,im,pm;
    int MIN = -1000, MAX = 1000;
    unordered_map<int,bool> M;

    void fill(bool clock, vector<vector<int>>& trees){

        x = ix;

        if(clock){

            y = MIN;
            pm = (float) MAX;

            for(int i=0;i<n;i++){
                if(trees[i][0]==x){
                    if(trees[i][1]>y) y = trees[i][1];
                } 
                if(trees[i][0]==xm) M[i]=true;
            }

        }
        else{

            y = MAX;
            pm = (float) MIN;

            for(int i=0;i<n;i++){
                if(trees[i][0]==x){
                    M[i] = true;
                    if(trees[i][1]<y) y = trees[i][1];
                } 
            }

        }

        bool brk = false;

        while(true){
            if(clock) im = (float) MIN;
            else im = (float) MAX;
            for(int i=0;i<n;i++){
                if(x==trees[i][0]) continue;
                m = ((float) (trees[i][1]-y))/((float) (trees[i][0]-x));
                if(clock && m<pm && m>im) im = m;
                if(!clock && m>pm && m<im) im = m;
            }
            if(im==MAX || im==MIN) break;
            dm = 0;
            pm = im;
            for(int i=0;i<n;i++){
                if(x==trees[i][0]) continue;
                m = ((float) (trees[i][1]-y))/((float) (trees[i][0]-x));
                if(m==pm){
                    if(ix==trees[i][0] || xm==trees[i][0]){
                        brk = true;
                        continue;
                    }
                    M[i] = true;
                    d = (trees[i][0]-x)*(trees[i][0]-x) + (trees[i][1]-y)*(trees[i][1]-y);
                    if(d>dm){
                        dm = d;
                        p = i;
                    } 
                } 
            }
            if(brk) break;
            x = trees[p][0];
            y = trees[p][1];
        }
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {

        ix = MAX;
        xm = MIN;
        n = trees.size(); 
        for(int i=0;i<n;i++){
            if(trees[i][0]<ix) ix = trees[i][0];
        }
        for(int i=0;i<n;i++){
            if(trees[i][0]>xm) xm = trees[i][0];
        }

        fill(true, trees);
        if(ix!=xm) fill(false, trees);

        vector<vector<int>> ans;
        for(auto i : M){
            if(i.second) ans.push_back(trees[i.first]);
        }

        return ans;
    }
};
23400