from itertools import combinations

def erect_the_fence_brute_force(points):

    potential_fences = []
    number_of_points = len(points)

    # Iterate through possible fence sizes
    for fence_size in range(3, number_of_points + 1):
        # Generate all combinations of points
        for point_indices in combinations(range(number_of_points), fence_size):
            fence_points = [points[index] for index in point_indices]
            remaining_points = [points[i] for i in range(number_of_points) if i not in point_indices]

            # Check if all remaining points are inside the fence
            if is_valid_fence(fence_points, remaining_points):
                potential_fences.append(fence_points)

    # Find the fence with the smallest area (or perimeter, etc.)
    if not potential_fences:
        return []
    best_fence = min(potential_fences, key=calculate_area)
    return best_fence

def is_valid_fence(fence_points, remaining_points):
    if len(fence_points) == 3:
        #For triangles, check all points are inside
        for point in remaining_points:
            if not is_point_inside_triangle(point, fence_points[0], fence_points[1], fence_points[2]):
                return False
        return True
    
    #For more complex shapes, check all points are inside
    convex_hull_points = convex_hull(fence_points)
    for point in remaining_points:
        if not is_point_inside_polygon(point, convex_hull_points):
            return False
    return True

def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1:
        return points

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower = []
    for point in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], point) <= 0:
            lower.pop()
        lower.append(point)

    upper = []
    for point in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], point) <= 0:
            upper.pop()
        upper.append(point)

    return lower[:-1] + upper[:-1]

def is_point_inside_triangle(point, a, b, c):
    def sign(p1, p2, p3):
        return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])

    d1 = sign(point, a, b)
    d2 = sign(point, b, c)
    d3 = sign(point, c, a)

    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)

    return not (has_neg and has_pos)

def is_point_inside_polygon(point, polygon_points):
    number_of_points = len(polygon_points)
    inside = False
    p1x, p1y = polygon_points[0]
    for i in range(1, number_of_points + 1):
        p2x, p2y = polygon_points[i % number_of_points]
        if point[1] > min(p1y, p2y):
            if point[1] <= max(p1y, p2y):
                if point[0] <= max(p1x, p2x):
                    if p1y != p2y:
                        intersection_x = (point[1] - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                    if p1x == p2x or point[0] <= intersection_x:
                        inside = not inside
        p1x, p1y = p2x, p2y
    return inside

def calculate_area(fence_points):
    #Dummy implementation. Calculate real area here.
    return len(fence_points)

# Example usage (replace with your actual points)
# points = [[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]
# fence = erect_the_fence_brute_force(points)
# print(fence)

def erect_the_fence(trees):
    def cross_product_length(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

    if len(trees) < 3:
        return trees

    # Sort points to easily construct the convex hull
    trees.sort(key=lambda point: (point[0], point[1]))

    lower_hull = []
    for point in trees:
        # Maintain counter-clockwise order in the lower hull
        while len(lower_hull) >= 2 and cross_product_length(lower_hull[-2], lower_hull[-1], point) < 0:
            lower_hull.pop()
        lower_hull.append(point)

    upper_hull = []
    for point in reversed(trees):
        # Maintain counter-clockwise order in the upper hull
        while len(upper_hull) >= 2 and cross_product_length(upper_hull[-2], upper_hull[-1], point) < 0:
            upper_hull.pop()
        upper_hull.append(point)

    # Combine the hulls, removing duplicates
    convex_hull = lower_hull[:-1] + upper_hull[:-1]

    # Remove duplicate points from the result.
    return list(set(map(tuple, convex_hull)))