1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Point implements Comparable<Point> {
6    int x, y;
7    Point(int x, int y) {
8        this.x = x;
9        this.y = y;
10    }
11    public int compareTo(Point p) {
12        return this.x == p.x ? this.y - p.y : this.x - p.x;
13    }
14}
15
16public class Main {
17    public static int cross(Point O, Point A, Point B) {
18        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
19    }
20
21    public static List<Point> convexHull(Point[] points) {
22        Arrays.sort(points);
23        List<Point> hull = new ArrayList<>();
24
25        for (int i = 0; i < points.length; i++) {
26            while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
27                hull.remove(hull.size() - 1);
28            hull.add(points[i]);
29        }
30
31        for (int i = points.length - 2, t = hull.size() + 1; i >= 0; i--) {
32            while (hull.size() >= t && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
33                hull.remove(hull.size() - 1);
34            hull.add(points[i]);
35        }
36
37        return hull.subList(0, hull.size() - 1);
38    }
39
40    public static void main(String[] args) {
41        Point[] trees = {new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2)};
42        List<Point> result = convexHull(trees);
43        System.out.println("Convex Hull:");
44        for (Point p : result)
45            System.out.println("(" + p.x + ", " + p.y + ")");
46    }
47}

1#include <vector>
using namespace std;

struct Point {
    int x, y;
};

int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    return val == 0 ? 0 : (val > 0 ? 1 : 2);
}

void convexHull(vector<Point>& points) {
    if (points.size() < 3) return;
    vector<Point> hull;

    int l = 0;
    for (int i = 1; i < points.size(); i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do {
        hull.push_back(points[p]);
        q = (p + 1) % points.size();

        for (int i = 0; i < points.size(); i++)
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;

        p = q;

    } while (p != l);

    cout << "Convex Hull:" << endl;
    for (auto& h : hull)
        cout << "(" << h.x << ", " << h.y << ")" << endl;
}

int main() {
    vector<Point> points = { {1, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {4, 2} };
    convexHull(points);
    return 0;
}