<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:
    std::vector < std::vector < int > > outerTrees ( std::vector < std::vector < int > > & trees ) {
        // First Check Whether All The Trees Form a Straight line or NOT !!!
        if ( trees.size() <= 3 ) { // 3 hole hoy Straight Line / TriAngle e biddoman ... ekhetre protita Node e Perimeter e obosthito hobe !!!
            return trees ;
        }
        int DY = trees[1][1] - trees[0][1] , DX = trees[1][0] - trees[0][0] , i = 0 ;
        bool Straight_Line = true ;
        if ( DY == 0 ) {
            for ( i = 2 ; i < trees.size() ; i++ ) {
                int dy = trees[i][1] - trees[0][1] ;
                if ( dy != 0 ) {
                    Straight_Line = false ; break ;
                }
            }
        }
        else if ( DX == 0 ) {
            for ( i = 2 ; i < trees.size() ; i++ ) {
                int dx = trees[i][0] - trees[0][0] ;
                if ( dx != 0 ) {
                    Straight_Line = false ; break ;
                }
            }
        }
        else {
            double M = double(DY) / DX ;
            for ( i = 2 ; i < trees.size() ; i++ ) {
                int dy = trees[i][1] - trees[0][1] , dx = trees[i][0] - trees[0][0] ;
                double m = double(dy) / dx ;
                if ( m != M ) {
                    Straight_Line = false ; break ;
                }
            }
        }
        if ( Straight_Line ) return trees ;
    //    std::cout <<"Here 1" <<std::endl ;
        int Furthest_Left = INT_MAX , Furthest_Right = INT_MIN ;
        for ( i = 0 ; i < trees.size() ; i++ ) {
            Furthest_Left = std::min ( Furthest_Left , trees[i][0] ) ;
            Furthest_Right = std::max ( Furthest_Right , trees[i][0] ) ;
        }
        std::vector < int > For_Furthest_Left_Y_Axis_Are , For_Furthest_Right_Y_Axis_Are ;
        for ( i = 0 ; i < trees.size() ; i++ ) {
            if ( trees[i][0] == Furthest_Left ) {
                For_Furthest_Left_Y_Axis_Are.push_back ( trees[i][1] ) ;
            }
            else if ( trees[i][0] == Furthest_Right ) {
                For_Furthest_Right_Y_Axis_Are.push_back ( trees[i][1] ) ;
            }
        }
        std::sort ( For_Furthest_Left_Y_Axis_Are.begin() , For_Furthest_Left_Y_Axis_Are.end() ) ;
        std::sort ( For_Furthest_Right_Y_Axis_Are.begin() , For_Furthest_Right_Y_Axis_Are.end() ) ;
        std::set < std::pair < int , int > > Set ; std::set < std::pair < int , int > > :: iterator Set_Ite ;
        for ( i = 0 ; i < For_Furthest_Left_Y_Axis_Are.size() ; i++ ) {
            Set.insert ( { Furthest_Left , For_Furthest_Left_Y_Axis_Are[i] } ) ;
        }
        for ( i = 0 ; i < For_Furthest_Right_Y_Axis_Are.size() ; i++ ) {
            Set.insert ( { Furthest_Right , For_Furthest_Right_Y_Axis_Are[i] } ) ;
        }
        std::pair < int , int > Origin1 = { Furthest_Left , For_Furthest_Left_Y_Axis_Are [ For_Furthest_Left_Y_Axis_Are.size() - 1 ] } ;
        std::pair < int , int > Origin2 = { Furthest_Left , For_Furthest_Left_Y_Axis_Are [ 0 ] } ;
        std::pair < int , int > Origin3 = { Furthest_Right , For_Furthest_Right_Y_Axis_Are [ For_Furthest_Right_Y_Axis_Are.size() - 1 ] } ;
        std::pair < int , int > Origin4 = { Furthest_Right , For_Furthest_Right_Y_Axis_Are [ 0 ] } ;
        std::pair < int , int > Curr_Pos = Origin1 ;
    //    std::cout <<"Here 2" <<std::endl ;
    //    std::cout <<"Origins ==> " <<Origin1.first <<" " <<Origin1.second <<" , " <<Origin2.first <<" " <<Origin2.second <<" , "
    //                               <<Origin3.first <<" " <<Origin3.second <<" , " <<Origin4.first <<" " <<Origin4.second <<std::endl ;
        double Pre_Slope = 100000000.0 ;
        while ( 1 ) {
            std::map < double , std::vector < std::pair < int , int > > > Map ; std::map < double , std::vector < std::pair < int , int > > > :: iterator Ite ;
            for ( i = 0 ; i < trees.size() ; i++ ) {
                if ( trees[i][0] != Curr_Pos.first ) {
                    int dy = trees[i][1] - Curr_Pos.second , dx = trees[i][0] - Curr_Pos.first ;
                    double Slope = double(dy) / dx ;
    //                std::cout <<Curr_Pos.first <<" " <<Curr_Pos.second <<" -- " <<trees[i][0] <<" " <<trees[i][1] <<"   --> " <<Slope <<std::endl ;
                    Map [ Slope ] . push_back ( { trees[i][0] , trees[i][1] } ) ;
                }
            }
            Ite = Map.lower_bound ( Pre_Slope ) ; Ite-- ;
            bool Origin3_Found = false ;
            for ( i = 0 ; i < Ite->second.size() ; i++ ) {
                if ( Ite->second[i] == Origin3 ) {
                    Origin3_Found = true ;
                }
                Set.insert ( Ite->second[i] ) ;
                if ( Ite->second[i].first > Curr_Pos.first ) {
                    Curr_Pos = Ite->second[i] ;
                }
            }
            if ( Origin3_Found ) {
                break ;
            }
            Pre_Slope = Ite->first ;
        }
        Curr_Pos = Origin4 ; Pre_Slope = 100000000.0 ;
        while ( 1 ) {
            std::map < double , std::vector < std::pair < int , int > > > Map ; std::map < double , std::vector < std::pair < int , int > > > :: iterator Ite ;
            for ( i = 0 ; i < trees.size() ; i++ ) {
                if ( trees[i][0] != Curr_Pos.first ) {
                    int dy = trees[i][1] - Curr_Pos.second , dx = trees[i][0] - Curr_Pos.first ;
                    double Slope = double(dy) / dx ;
                    Map [ Slope ] . push_back ( { trees[i][0] , trees[i][1] } ) ;
                }
            }
            Ite = Map.lower_bound ( Pre_Slope ) ; Ite-- ;
            bool Origin2_Found = false ;
            for ( i = 0 ; i < Ite->second.size() ; i++ ) {
                if ( Ite->second[i] == Origin2 ) {
                    Origin2_Found = true ;
                }
                Set.insert ( Ite->second[i] ) ;
                if ( Ite->second[i].first < Curr_Pos.first ) {
                    Curr_Pos = Ite->second[i] ;
                }
            }
            if ( Origin2_Found ) {
                break ;
            }
            Pre_Slope = Ite->first ;
        }
        std::vector < std::vector < int > > Res ;
        for ( Set_Ite = Set.begin() ; Set_Ite != Set.end() ; Set_Ite++ ) {
            Res.push_back ( { Set_Ite->first , Set_Ite->second } ) ;
        }
        return Res ;
    }
};
69000