using System;

using System.Linq;

using System.Collections.Generic;

​

class ClosestPair

{

    public class Point

    {

        public double x, y;

        public Point(double x, double y)

        {

            this.x = x;

            this.y = y;

        }

    }

​

    public class CompareByX : IComparer<Point>

    {

        public int Compare(Point p1, Point p2)

        {

            return p1.x.CompareTo(p2.x);

        }

    }

​

    public class CompareByY : IComparer<Point>

    {

        public int Compare(Point p1, Point p2)

        {

            return p1.y.CompareTo(p2.y);

        }

    }

​

    private static double Distance(Point p1, Point p2)

    {

        return Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));

    }

​

    private static double ClosestPairRec(Point[] pointsX, Point[] pointsY, int left, int right)

    {

        if (right - left <= 3)

        {

            return BruteForceClosestPair(pointsX, left, right);

        }

​

        int mid = (left + right) / 2;

        Point midPoint = pointsX[mid];

        Point[] leftPointsY = pointsY.Where(p => p.x <= midPoint.x).ToArray();

        Point[] rightPointsY = pointsY.Where(p => p.x > midPoint.x).ToArray();

        double leftClosest = ClosestPairRec(pointsX, leftPointsY, left, mid);

        double rightClosest = ClosestPairRec(pointsX, rightPointsY, mid + 1, right);

        double minDist = Math.Min(leftClosest, rightClosest);

        double crossClosest = ClosestPairAcrossSplitLine(pointsX, pointsY, minDist, midPoint, left, right);

        return Math.Min(minDist, crossClosest);

    }

​

    private static double BruteForceClosestPair(Point[] points, int left, int right)

    {

        double minDist = double.MaxValue;

        for (int i = left; i < right; i++)

        {

            for (int j = i + 1; j <= right; j++)

            {

                minDist = Math.Min(minDist, Distance(points[i], points[j]));

            }

        }

​

        return minDist;

    }

​

    private static double ClosestPairAcrossSplitLine(Point[] pointsX, Point[] pointsY, double delta, Point midPoint, int left, int right)

    {

        var strip = pointsY.Where(p => Math.Abs(p.x - midPoint.x) < delta).ToArray();

        double minDist = delta;

        for (int i = 0; i < strip.Length; i++)

        {

            for (int j = i + 1; j < strip.Length && (strip[j].y - strip[i].y) < minDist; j++)

            {

                minDist = Math.Min(minDist, Distance(strip[i], strip[j]));

            }

        }

​

        return minDist;

    }

​

    public static double FindClosestPair(Point[] points)

    {

        Point[] pointsX = points.OrderBy(p => p.x).ToArray();

        Point[] pointsY = points.OrderBy(p => p.y).ToArray();

        return ClosestPairRec(pointsX, pointsY, 0, points.Length - 1);

    }

​

    public static void Main(string[] args)

    {

        // Define some test points

        Point[] points = new Point[]

        {

            new Point(2, 3),

            new Point(12, 30),

            new Point(40, 50),

            new Point(5, 1),

            new Point(12, 10),

            new Point(3, 4)

        };

        double closestDist = FindClosestPair(points);

        Console.WriteLine("The closest pair distance is: " + closestDist.ToString("F2"));

    }

}