TopCoder SRM 614: MinimumSquare

解説は、TopCoder SRM614 解説 を参考にしてください。

\(O(N^3)\) 解です。

public class MinimumSquare {
    struct Point {
        public long X, Y;
    }

    public long minArea(int[] x, int[] y, int K) {
        var points = x.Zip(y, (X, Y) => new Point { X = X, Y = Y })
            .OrderBy(p => p.Y)
            .ToArray();
        long ans = long.MaxValue;

        var xs = x.Distinct().ToArray();
        Array.Sort(xs);

        for (int j = 0; j < xs.Length; j++) {
            for (int i = 0; i <= j; i++) {
                var listY = new List<int>();
                long width = xs[j] - xs[i];
                var pointsInXRange = points
                    .Where(p => xs[i] <= p.X && p.X <= xs[j])
                    .ToArray();
                var minHeight = pointsInXRange.Zip(pointsInXRange.Skip(K - 1), (p1, pK) => pK.Y - p1.Y)
                    .DefaultIfEmpty(long.MaxValue)
                    .Min();
                if (minHeight == long.MaxValue) continue;
                var side = Math.Max(width, minHeight) + 2;
                ans = Math.Min(ans, side * side);
            }
        }

        return ans;
    }
}