ZOJ 3664 Split the Rectangle | The 2012 ACM-ICPC Asia Changchun Regional Contest – J

题目： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3664

矩形间的包含关系可以用一棵二叉树来表示（像线段树），最后去掉的矩形是A， B所在的最小矩形的LCA的所有子节点；

对每个矩形存其子节点的个数，每次询问时dfs找到A，B的LCA（第一次搜到的A，B不在一起的矩形），答案就是N-这个LCA的子节点数+1；

这换行略奇葩啊=_=!!

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
#define MAXN 4010
struct Rectangle {
    int xl, yl, xr, yr, l, r, cnt;
}rect[MAXN];

struct Segment {
    int xl, yl, xr, yr;
}seg[MAXN];

struct Point {
    int x, y;
}A, B;

int N, Q, cnt;
inline bool is_in(int l, int m, int r) {
    return (l < m && m < r);
}
int build(Rectangle node, int vertical) {
    rect[cnt] = node;
    rect[cnt].l = rect[cnt].r = -1;
    rect[cnt].cnt = 0;
    int res = cnt++;
    for (int i = 0; i < N; i++) {
        if ( (seg[i].yl == seg[i].yr) ^ vertical) {
            if (vertical) {
                if (is_in(node.xl, seg[i].xl, node.xr) && seg[i].yl == node.yl && seg[i].yr == node.yr) {
                    Rectangle tmp = node;
                    tmp.xr = seg[i].xl;
                    rect[res].l = build(tmp, vertical^1);

                    tmp = node;
                    tmp.xl = seg[i].xl;
                    rect[res].r = build(tmp, vertical^1);
                }
            } else {
                if (is_in(node.yl, seg[i].yl, node.yr) && seg[i].xl == node.xl && seg[i].xr == node.xr) {
                    Rectangle tmp = node;
                    tmp.yr = seg[i].yl;
                    rect[res].l = build(tmp, vertical^1);

                    tmp = node;
                    tmp.yl = seg[i].yl;
                    rect[res].r = build(tmp, vertical^1);
                }
            }
        }
    }
    if (rect[res].l == -1 && rect[res].r == -1)
        rect[res].cnt = 1;
    else {
        if (rect[res].l != -1) rect[res].cnt += rect[rect[res].l].cnt;
        if (rect[res].r != -1) rect[res].cnt += rect[rect[res].r].cnt;
    }
    return res;
}
bool is_contain(Rectangle r, Point a) {
    return r.xl < a.x && a.x < r.xr && r.yl < a.y && a.y < r.yr;
}
int dfs(Rectangle node) {
    if (node.l != -1) {
        if (is_contain(rect[node.l], A) && is_contain(rect[node.l], B))
            return dfs(rect[node.l]);
    }
    if (node.r != -1) {
        if (is_contain(rect[node.r], A) && is_contain(rect[node.r], B))
            return dfs(rect[node.r]);
    }
    return node.cnt;
}
int main()
{
    while (scanf("%d%d%d%d", &rect[0].xl, &rect[0].yl, &rect[0].xr, &rect[0].yr) == 4) {
        scanf("%d%d", &N, &Q);
        for (int i = 0; i < N ; i++) {
            scanf("%d%d%d%d", &seg[i].xl, &seg[i].yl, &seg[i].xr, &seg[i].yr);
            if (seg[i].xl > seg[i].xr)  swap(seg[i].xl, seg[i].xr);
            if (seg[i].yl > seg[i].yr)  swap(seg[i].yl, seg[i].yr);
        }
        cnt = 0;
        build(rect[0], 0);
        for (int i = 0 ; i < Q; i++) {
            scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y);
            printf ("%dn", N+2-dfs(rect[0]));
        }
    }
    return 0;
}

• Regional Asia