<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>

using P2I = pair<int, int>;
class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        int n = trees.size();
        if(n<4) return trees;

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

        unordered_set<int> fences;
        int p = left_most;
        do{
            int q = (p+1) % n;
            for(int i=0; i<n; i++){
                if(fences.find(i)!=fences.end()) continue;

                if(orientation(trees[p], trees[i], trees[q])<0) q=i;
            }
            for(int i=0; i<n; i++){
                if(i!=p && i!=q && orientation(trees[p], trees[i], trees[q])==0 && inBetween(trees[p], trees[i], trees[q])){
                    fences.insert(i);
                }
            }
            p = q;
            fences.insert(q);
        }while(p!=left_most);

        vector<vector<int>> res;
        for(auto node: fences) res.push_back(trees[node]);
        return res;
    }

    int orientation(vector<int>& p, vector<int>& q, vector<int>& r){
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    bool inBetween(vector<int>& p, vector<int>& i, vector<int>& q) {
        bool a = (i[0] >= p[0] && i[0] <= q[0]) || (i[0] <= p[0] && i[0] >= q[0]);
        bool b = (i[1] >= p[1] && i[1] <= q[1]) || (i[1] <= p[1] && i[1] >= q[1]);
        return a && b;
    }
};
23500