USACO 5.3 Window Area

Maintain an array of windows and an array of levels maps to each window. Bring a window top / down is easy, just change the levels. Destroy a window is also easy. To draw the visible surface of window, consider the drawing process a series of culling with the windows with a higher level than it. At each step, there are several cases: not culling, partial culling, or completely culling. After each step we either get the end result or in case of partial culling, we repeat same step again until we hit the top level window. DFS is a natural fit here.

One note is the input data has to be normalized first (the corners of the window could be top-left/bottom-right or bottom-left/top-right).

#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

const int N = 70;
const int M = 500;
int total = -1, ans = 0;

typedef struct window {
    int u, d, l, r;
} tWindow;

vector<tWindow> windows(M);
vector<char> order(N);

void dfs(int u /*up*/, int l /*left*/, int d /*down*/, int r /*right*/,
         int level) {
    if(level > total) {
        ans += (u - d) * (r - l);
        return;
    }
    int i = order[level];
    tWindow w = windows[i];
    if(u <= w.d || d >= w.u || l >= w.r || r <= w.l ) {
        dfs(u, l, d , r, level + 1); /* no intersection */
    } else if(u <= w.u && d >= w.d && l >= w.l && r <= w.r ) {
        return; /* absorbed */
    } else {
        if (d < w.u && w.u < u) {
            dfs(u, l, w.u, r, level + 1);
        }
        if (d < w.d && w.d < u) {
            dfs(w.d, l, d, r, level + 1);
        }
        // avoid duplicate compute
        u = std::min(u, w.u);
        d = std::max(d, w.d);
        if(w.l > l && w.l < r) {
           dfs(u, l, d, w.l, level + 1);
        }
        if(w.r > l && w.r < r) {
           dfs(u, w.r, d, r, level + 1);
        }
    }
}

int main() {
    ifstream fin("window.in");
    ofstream fout("window.out");
    char op, id, s;
    int i, u, d, l, r;
    while(fin >> op) {
        if(op == 'w') {
            fin >> s >> id >> s >> l >> s >> u >> s >> r >> s >> d >> s;
            if(d > u) swap(d,u);
            if(l > r) swap(l,r);
            windows[id].u = u; windows[id].d=d;
            windows[id].l=l; windows[id].r=r;
            total++;
            order[total] = id;
        } else if(op == 't'|| op == 'd') {
            fin >> s >> id >> s;
            for(i = 0; i < total; ++i) {
                if(order[i] == id) swap(order[i],order[i + 1]);
            }
            if(op == 'd') total--;
        }
        else if(op == 'b') {
            fin >> s >> id >> s;
            for(i = total; i > 0; --i) {
                if(order[i] == id) swap(order[i],order[i - 1]);
            }
        } else {
            fin >> s >> id >> s;
            for(i = 0; i <= total; ++i) {
                if(order[i] == id) {
                    ans = 0;
                    tWindow w = windows[id];
                    u = (w.u - w.d) * (w.r - w.l);
                    dfs(w.u, w.l, w.d, w.r, i + 1);
                    fout << std::fixed << std::setprecision(3)
                         << 100.0 * ans / u << endl;
                    break;
                }
            }
        }
    }
    return 0;
}