这次用了矩形分割的方法实现了下，参考了这的代码，用了上浮+矩形分割的思想，个人觉得递归的写法更形象，且方便，于是，看了04年薛矛大牛论文后，实现了这个方法，觉得很赞，先从X方向上割掉，再割掉Y方向上。不过最糟糕复杂度是O(N^3)，这个还是很可怕的，但一般是达不到的，这里的11个数据，都在0.1s以下，这种方法是解决一类统计类问题的利器~
下面是薛大牛论文中的伪码：
下面是用矩形分割实现该题的代码：
/* ID: litstrong PROG: rect1 LANG: C++ */ #include <iostream> #include <string> #include <vector> #include <set> #include <math.h> #include <queue> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; const int MAXN = 10005; const int MAXC = 2505; int c_ans[MAXC]; int A, B, N; class CRECT { public: int nx, mx, ny, my, c; public: CRECT() {} CRECT(int _nx, int _mx, int _ny, int _my, int _c) : nx(_nx), mx(_mx), ny(_ny), my(_my), c(_c) {} }rect[MAXN]; void CutFloat(int level, int x1, int y1, int x2, int y2, int c) { if(level > N) { c_ans[c] += (x2 - x1) * (y2 - y1); return; } int x3 = rect[level].nx, y3 = rect[level].ny; int x4 = rect[level].mx, y4 = rect[level].my; if(x3 >= x2 || x4 <= x1 || y3 >= y2 || y4 <= y1) CutFloat(level + 1, x1, y1, x2, y2, c); else { int k1, k2, k3, k4; //x k1 = max(x1, x3); k2 = min(x2, x4); if(x1 < k1) CutFloat(level + 1, x1, y1, k1, y2, c); if(k2 < x2) CutFloat(level + 1, k2, y1, x2, y2, c); //y k3 = max(y1, y3); k4 = min(y2, y4); if(y1 < k3) CutFloat(level + 1, k1, y1, k2, k3, c); if(k4 < y2) CutFloat(level + 1, k1, k4, k2, y2, c); } } int main() { freopen("rect1.in", "r", stdin); freopen("rect1.out", "w", stdout); scanf("%d%d%d", &A, &B, &N); rect[0] = CRECT(0, A, 0, B, 1); for(int i = 1; i <= N; i++) { int nx, mx, ny, my, c; scanf("%d%d%d%d%d", &nx, &ny, &mx, &my, &c); rect[i] = CRECT(min(nx, mx), max(nx, mx), min(ny, my), max(ny, my), c); } memset(c_ans, 0, sizeof(c_ans)); //上浮 for(int i = N; i >= 0; i--) { CutFloat(i + 1, rect[i].nx, rect[i].ny, rect[i].mx, rect[i].my, rect[i].c); } for(int i = 0; i < MAXC; i++) if(c_ans[i]) printf("%d %d\n", i, c_ans[i]); }转载于:https://www.cnblogs.com/litstrong/archive/2011/03/06/1972271.html
相关资源：数据结构—成绩单生成器