Problem E: Chainsaw Massacre

Background 

As every year the Canadian Lumberjack Society has just held its annual woodcutting competition and the national forests between Montreal and Vancouver are devastated. Now for the social part! In order to lay out an adequate dance floor for the evening party the organizing committee is looking for a large rectangular area without trees. Naturally, all lumberjacks are already drunk and nobody wants to take the risk of having any of them operate a chainsaw.

The Problem 

The organizing committee has asked you to find the largest yet free rectangle which could serve as the dance floor. The area in which you should search is also rectangular and the dance floor must be entirely located in that area. Its sides should be parallel to the borders of the area. It is allowed that the dance floor is located at the borders of the area and also that trees grow on the borders of the dance floor. What is the maximum size of the dance floor?

The Input 

The first line of the input specifies the number of scenarios. For each scenario, the first line provides the length l and width w of the area in meters ( , both integers). Each of the following lines describes either a single tree, or a line of trees according to one of the following formats:

• 1 x y, where the ``one'' characterizes a single tree, and x and y provide its coordinates in meters with respect to the upper left corner.
• k x y dx dy, where k>1 provides the number of trees in a line with coordinates .
• 0 denotes the end of the scenario.

The coordinates x, y, dx, and dy are given as integers. It is guaranteed that all the trees are situated in the area, i.e. have coordinates in . There will be at most 1000 trees.

The Output 

For each scenario print a line containing the maximum size of the dance floor measured in square meters.

Sample Input 

2
2 3
0
10 10
2 1 1 8 0
2 1 9 8 0
0

Sample Output 

6
80

---

Miguel Revilla
2000-11-19

我就偷偷盜用 DJWS 的演算法筆記的圖片了





x, y 軸兩個都要做嘗試基底的動作。
考慮一下都是 x = ? 當做基底時, 如果 y 值與窮舉點一樣, 那麼可選上或選下,
但無法決定哪個好，但是可以被決定於 y = ? 當做基底時的窮舉。

整體效率是 O(n*n)


#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b){}
    bool operator<(const Pt &p) const {
        if(p.x != x)
            return x < p.x;
        return y < p.y;
    }
};
bool cmp(Pt a, Pt b) {
    if(a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
Pt tree[3000];
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        int h, w;
        int x, y, dx, dy;
        scanf("%d %d", &h, &w);
        int op, i, j;
        int n = 0;
        tree[n++] = Pt(0,0);
        tree[n++] = Pt(h,w);
        tree[n++] = Pt(h,0);
        tree[n++] = Pt(0,w);
        while(scanf("%d", &op) == 1 && op) {
            scanf("%d %d", &x, &y);
            if(op != 1)
                scanf("%d %d", &dx, &dy);
            for(i = 0; i < op; i++) {
                tree[n++] = Pt(x, y);
                x += dx, y += dy;
            }
        }
        sort(tree, tree+n);
        int area = 0;
        for(i = 0; i < n; i++) {
            int mny = 0, mxy = w;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].x-tree[i].x)*(mxy-mny));
                if(tree[j].x == tree[i].x)
                    continue;
                if(tree[j].y > tree[i].y)
                    mxy = min(mxy, tree[j].y);
                else
                    mny = max(mny, tree[j].y);
            }
        }
        sort(tree, tree+n, cmp);
        for(i = 0; i < n; i++) {
            int mnx = 0, mxx = h;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].y-tree[i].y)*(mxx-mnx));
                if(tree[j].y == tree[i].y)
                    continue;
                if(tree[j].x > tree[i].x)
                    mxx = min(mxx, tree[j].x);
                else
                    mnx = max(mnx, tree[j].x);
            }
        }
        printf("%d\n", area);

    }
    return 0;
}