I’m trying to solve this question on leetcode but I encountered some difficulties.
Here’s the question: 587. Erect the Fence

Here are the potential issues I’ve identified in my code:

1. Upper and Lower Tangent Calculation: The logic to find the upper and lower tangents might be incorrect, leading to an improper merge of the hulls.
2. Merging Hulls: The merging process of the left and right hulls might not correctly handle all edge cases.

I use the divide & conquer algorithm. I divide the points into two small hull(left and right), then merge them by finding upper and lower tangent. Unfortunately, my solution is incorrect. Could you please help me identify the issue?

Below is my code. BTW I know there are others algorithms to solve convex hull problem but I am currently learning from MIT’s 6.046 course, so I want to use divide and conquer.

struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int a, int b) : x(a), y(b) {}
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

class Solution {
public:
    int crossProduct(const Point& a, const Point& b, const Point& c) {
        int u_x = b.x - a.x;
        int u_y = b.y - a.y;
        int v_x = c.x - a.x;
        int v_y = c.y - a.y;
        // 外積 > 0 左
        return u_x * v_y - u_y * v_x;
    }
    
    vector<Point> merge(const vector<Point>& left, const vector<Point>& right) {
        int n1 = left.size(), n2 = right.size();
        int i = 0, j = 0;
        // 找左邊 hull 的最右點
        for(int k=1; k<n1; k++) {
            if(left[k].x > left[i].x || (left[k].x == left[i].x && left[k].y > left[i].y)) {
                i = k;
            }
        }
        // 找右邊 hull 的最左點
        for(int k=1; k<n2; k++) {
            if(right[k].x < right[j].x || (right[k].x == right[j].x && right[k].y < right[j].y)) {
                j = k;
            }
        }

        // finding upper tangent
        int upper_i = i, upper_j = j;
        bool done = false;
        while(!done) {
            done = true;
            while(crossProduct(right[upper_j], left[upper_i], left[(upper_i + 1) % n1]) > 0) {
                // (upper_i + 1) % n1 -> counter clockwise of left hull
                upper_i = (upper_i + 1) % n1;
            }
            while(crossProduct(left[upper_i], right[upper_j], right[(upper_j - 1 + n2) % n2]) < 0) {
                upper_j = (upper_j - 1 + n2) % n2;
                done = false;
            }
        }

        // finding lower tangent
        done = false;
        int lower_i = i, lower_j = j;
        while(!done) {
            done = true;
            while(crossProduct(right[lower_j], left[lower_i], left[(lower_i - 1 + n1) % n1]) < 0) {
                // left -> clockwise
                lower_i = (lower_i - 1 + n1) % n1;
            }
            while(crossProduct(left[lower_i], right[lower_j], right[(lower_j + 1) % n2]) > 0) {
                lower_j = (lower_j + 1) % n2;
                done = false;
            }
        }

        // merge left and right with the points sorted in anti-clockwise order
        vector<Point> hull;
        int idx = upper_i;
        hull.push_back(left[idx]);
        while(idx != lower_i) {
            idx = (idx + 1) % n1;
            hull.push_back(left[idx]);
        }
        idx = lower_j;
        hull.push_back(right[idx]);
        while(idx != upper_j) {
            idx = (idx + 1) % n2;
            hull.push_back(right[idx]);
        }

        return hull;
    }

    // divide step
    vector<Point> convexHull(vector<Point>& points, int l, int r) {
        if(r - l + 1 <= 3) {
            vector<Point> hull(points.begin() + l, points.begin() + r + 1);
            sort(hull.begin(), hull.end(), [](const Point& a, const Point& b) {
                if(a.x == b.x) return a.y < b.y;
                return a.x < b.x;
            });
            return hull;
        }

        int mid = l + (r - l) / 2;
        vector<Point> leftHull = convexHull(points, l, mid);
        vector<Point> rightHull = convexHull(points, mid + 1, r);
        return merge(leftHull, rightHull);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        vector<Point> points;
        for(auto &p : trees) points.push_back(Point(p[0], p[1]));
        sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
            if(a.x == b.x) return a.y < b.y;
            return a.x < b.x;
        });
        // for(auto&it:points) cout<<it.x<<' '<<it.y<<endl;
        vector<Point> hull = convexHull(points, 0, points.size() - 1);
        vector<vector<int>> res;
        for(auto &p : hull) {
            res.push_back({p.x, p.y});
        }
        return res;
    }
};