使用C#寻找极值点-凸包

using System;
using System.Collections.Generic;

public class Point
{
    public double X { get; set; }
    public double Y { get; set; }
}

public class ConvexHull
{
    private static int CompareByPolarAngle(Point p1, Point p2)
    {
        if (p1.Y < p2.Y)
            return -1;
        if (p1.Y > p2.Y)
            return 1;
        if (p1.X < p2.X)
            return -1;
        if (p1.X > p2.X)
            return 1;
        return 0;
    }

    private static double CrossProduct(Point p0, Point p1, Point p2)
    {
        return (p1.X - p0.X) * (p2.Y - p0.Y) - (p1.Y - p0.Y) * (p2.X - p0.X);
    }

    public static List<Point> FindConvexHull(List<Point> points)
    {
        if (points.Count < 3)
            throw new ArgumentException("The number of points should be at least 3.");

        // Find the lowest point
        Point p0 = points[0];
        foreach (var point in points)
        {
            if (point.Y < p0.Y || (point.Y == p0.Y && point.X < p0.X))
                p0 = point;
        }

        // Sort points by polar angle
        points.Sort((p1, p2) => CompareByPolarAngle(p1, p2));

        // Build the convex hull
        Stack<Point> stack = new Stack<Point>();
        stack.Push(p0);
        stack.Push(points[1]);

        for (int i = 2; i < points.Count; i++)
        {
            while (stack.Count >= 2 && CrossProduct(stack.ElementAt(1), stack.Peek(), points[i]) <= 0)
                stack.Pop();
            stack.Push(points[i]);
        }

        return new List<Point>(stack);
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        List<Point> points = new List<Point>
        {
            new Point { X = 0, Y = 0 },
            new Point { X = 1, Y = 1 },
            new Point { X = 2, Y = 2 },
            new Point { X = 3, Y = 1 },
            new Point { X = 2, Y = 0 },
            new Point { X = 1, Y = 2 }
        };

        List<Point> convexHull = ConvexHull.FindConvexHull(points);

        foreach (var point in convexHull)
        {
            Console.WriteLine($"({point.X}, {point.Y})");
        }
    }
}