TopCoder SRM602: PilingRectsDiv2

まず、長方形が幅＜高さになるように回転させる。
あとは、共通部分の領域面積が limit 以下であるような２つの長方形のペアを全通り選ぶ。
それぞれのペアについて、共通部分の短形を完全に内包する他の長方形の個数 m としたとき、 m + 2 の最大値を求めれば良い。

ただしこれだけだと、長方形を１つだけ選ぶ場合に対応できてないのでそれは別途処理する。計算量は O(N^3)

public class PilingRectsDiv2 {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }

    struct Point { public int X, Y;}
    public int getmax(int[] X, int[] Y, int limit) {
        var points = X.Zip(Y, (x, y) => new Point() { X = x, Y = y }).ToArray();
        int n = points.Length;
        for (int i = 0; i < points.Length; i++) {
            if (points[i].X > points[i].Y)
                Swap(ref points[i].X, ref points[i].Y);
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (points[i].X * points[i].Y >= limit) ans = Math.Max(ans, 1);
            for (int j = 0; j < i; j++) {
                int w = Math.Min(points[i].X, points[j].X);
                int h = Math.Min(points[i].Y, points[j].Y);
                if (w * h < limit) continue;
                int cnt = 2 ;
                for (int k = 0; k < n; k++) {
                    if (i == k || j == k) continue;
                    if (points[k].X >= w && points[k].Y >= h)
                        cnt++;
                }
                ans = Math.Max(ans, cnt);
            }
        }

        return ans;
    }
}