itint5 Place WIndow - 摆放窗口

http://www.meetqun.com/thread-3247-1-1.html
有一个H * W的屏幕，左上角坐标为(0,0)，右下角坐标为(H,W)。屏幕中已有n个与坐标轴平行的矩形窗口，存放在数组rects中，第i个矩形窗口的左上坐标为(rects【i】.x1, rects【i】.y1)，右下坐标为(rects【i】.x2, rects【i】.y2)。现需要放置一个h * w的新矩形窗口，使得新窗口与已有的窗口重叠的总面积最小。请计算最小的重叠总面积。)
已知条件：
• 已有的窗口都完全在屏幕中。
• 摆放的新窗口也要完全在屏幕中。
• 已有的窗口互相不重叠。
• W, H<=10000，n<=100。

http://www.cnblogs.com/lautsie/p/3529643.html

一种做法是：把矩形所占的方格都设为-1，就是个最大子矩阵和问题。复杂度o(w^2*h)或o(w*h^2)，空间W*H
猜想应用场景是：电脑屏幕上已经有了n个聊天框，新建一个聊天框，放在屏幕的哪个位置最好。客户端计算的话，空间复杂度太高的算法应该是没法实际应用的。这种方法OJ也会空间超出。

另一种做法（贪心思想，和一个矩形覆盖最小）：
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
总可以找到一个满足最小覆盖条件的矩形，这个矩形的边要么与大窗口的边缘重合，要么和已知矩形的边重合。可以使用常见的贪心思想证明，假设有任意一个满足最小覆盖条件的矩形，总可以将其移动到与已有的边重合。

这样，只需要枚举O(n^2)的左上点坐标，总的时间复杂度O(n^3)。

可以这样理解，假设已经把矩形放在一个位置了，先只考虑上下移动（左右同理），那么在上下边遇到另一条横边之前，往上移动覆盖面积要么单调递增要么单调递减（也可以覆盖不变），往下移动单调性相反。那么总能移动到和某一条边重合并比原来覆盖面积相等或更小的。所以假设已经找到一个满足最小覆盖条件的矩形，那么可以将其移动到与已有的边重合。
注意：求两个矩形相交部分的面积的写法也很值得参考。

int calOverlapping(Rect &a, Rect &b) {

    int x = max(0, min(a.x2, b.x2) - max(a.x1, b.x1));

    int y = max(0, min(a.y2, b.y2) - max(a.y1, b.y1));

    return x * y;

}

int minOverlapping(vector<Rect> &rects, int W, int H, int w, int h) {

    if (rects.size() == 0) return 0;

    vector<int> x, y;

    x.push_back(0); x.push_back(H-h);

    y.push_back(0); y.push_back(W-w);

     

    for (int i = 0; i < rects.size(); i++) {

        if (rects[i].x1 - h >= 0) x.push_back(rects[i].x1 - h);

        if (rects[i].y1 - w >= 0) y.push_back(rects[i].y1 - w);

        if (rects[i].x2 + h <= H) x.push_back(rects[i].x2);

        if (rects[i].y2 + w <= W) y.push_back(rects[i].y2);

    }

     

    int ans = w * h; // max is fully overlapped

    for (int i = 0; i < x.size(); i++) {

        for (int j = 0; j < y.size(); j++) {

            Rect r;

            r.x1 = x[i]; r.x2 = x[i] + h;

            r.y1 = y[j]; r.y2 = y[j] + w;

            int cal = 0;

            for (int k = 0; k < rects.size(); k++) {

                cal += calOverlapping(rects[k], r);

            }

            if (cal < ans) ans = cal;

        }

    }

    return ans;

}

http://www.meetqun.com/thread-3247-1-1.html
    public int minOverlapping(Rect[] rects, int W, int H, int w, int h) {
                if (rects.length == 0) {
                        return 0;
                }
                // All possible left top coordinate <x, y> for the candidate rectangle.8 t. T6 m)
                ArrayList<Integer> x = new ArrayList<Integer>();
                ArrayList<Integer> y = new ArrayList<Integer>();5 M(
                x.add(0);
                x.add(H - h);
                y.add(0);
                y.add(W - w);
                for (Rect rect : rects) {
            if (rect.x1 - h >= 0) {
                x.add(rect.x1 - h);  }:
            }
            if (rect.y1 - w >= 0) {
                y.add(rect.y1 - w);
            }( Y! v7 j. X. S7 N' u- ]% ^
            if (rect.x2 + h <= H) {
                x.add(rect.x2);
            }
            if (rect.y2 + w <= W) {
                y.add(rect.y2);
            }
                }
                ) x9 m1 k6 [5 ^
                int result =  w * h; // max overlapped area is fully overlapped' L.
                for (int i = 0; i < x.size(); i++) {
                        for (int j = 0; j < y.size(); j++) {
                                Rect rect = new Rect(x.get(i), y.get(j), x.get(i) + h, y.get(j) + w);  // One candidate rectangle
                                int area = 0;  // Total overlapped area!
                                for (Rect rectangle : rects) {
                                        area += calculateOverlapping(rectangle, rect);
                                }
                                result = Math.min(result, area);
                        }
                }
                return result;3 ~5 R+ L, x9 X8 F
    }
          ]
        // Calculate the overlapped area for rectangle a and b.
        private int calculateOverlapping(Rect a, Rect b) {
                int x = Math.max(0, Math.min(a.x2, b.x2) - Math.max(a.x1, b.x1));
                int y = Math.max(0, Math.min(a.y2, b.y2) - Math.max(a.y1, b.y1));
                return x * y;
         }
}

Max Sub Matrix
https://github.com/zdzapple/itint5/blob/master/%E6%91%86%E6%94%BE%E7%AA%97%E5%8F%A3.cpp
int maxConsSum(const vector<int> &arr, int w, int row)
{
int n = arr.size();

int curSum = 0;
for (int j = 0; j < w; ++ j)
    {
curSum += arr[j];
    }

    int maxSum = curSum;
for (int i = w; i <= n - 1; ++ i)
{
curSum = curSum - arr[i-w];
curSum += arr[i];
maxSum = max(curSum, maxSum);
}
return maxSum;
}

int minOverlapping(vector<Rect> &rects, int W, int H, int w, int h)
{
if (rects.empty())
return 0;
vector<vector<int> > matrix(H, vector<int>(W, 0));
for (int i = 0; i < rects.size(); ++ i)
{
for (int row = rects[i].x1; row < rects[i].x2; ++ row)
{
for (int col = rects[i].y1; col < rects[i].y2; ++ col)
{
matrix[row][col] = -1;
}
}
}
int result = INT_MIN;
vector<int> subMatrix(matrix[0].size(), 0);
for (int row = 0; row < H - h + 1; ++ row)
{
if (row == 0)
for (int j = row; j < row + h; ++ j)
{
for (int k = 0; k < matrix[0].size(); ++ k)
{
subMatrix[k] += matrix[j][k];
}
}
else {
for (int k = 0; k < matrix[0].size(); ++ k)
{
subMatrix[k] -= matrix[row-1][k];
subMatrix[k] += matrix[row+h-1][k];
}
}

result = max(result, maxConsSum(subMatrix, w, row));
}
return 0 - result;
}