题目描述
N(N<5000) 张矩形的海报，照片和其他同样形状的图片贴在墙上。它们的边都是垂直的或水平的。每个矩形可以部分或者全部覆盖其他矩形。所有的矩形组成的集合的轮廓称为周长。写一个程序计算周长。
图 1 是一个有 7 个矩形的例子：
图 1.一个 7 个矩形的集合对应的轮廓为图 2 所示的所有线段的集合：
图 2. 矩形集合的轮廓
所有矩形的顶点坐标均为整数。所有的坐标都在 [-10000，10000] 的范围内，并且任何一个矩形面积都为整数。结果的值可能需要 32 位有符号整数表示。
输入
第1行: N，张贴在墙上的矩形的数目
第 2..N+1行 接下来的N行中，每行都有两个点的坐标，分别是矩形的左下角坐标和右上角坐标。每一个坐标由 X 坐标和 Y 坐标组成。
输出
只有一行，为一个非负整数，表示输入数据中所有矩形集合的轮廓长度。
样例输入
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16样例输出
228来源
IOI1998
其实这道题根本不需要什么覆盖层数，直接排序+暴力就能跑出0ms（洛谷0ms，FZOJ 4ms）.
我们开一个数组highest，highest[i]存储[i, i+1)这条线段上所有已经搜过的矩形的最高的上边的高度。如果现在正在搜的矩形的最低边高于已经搜过的，则中间就会有一层没贴的，于是需要计入总周长。
怎么处理能使得搜到这个矩形时，所搜到的最高的上边的高度不再会覆盖掉这个矩形呢？其实只要根据矩形的下表面从下至上的顺序排序，这样就能保证以后搜到的矩形只会往上走，最高值只会越来越高，而不会突然又搜到下面的矩形，导致重复统计了。
时间复杂度O(n log n + n × (maxx - minx) + n × (maxy - miny))。如果加入离散，则最坏时间复杂度为O(n2)。
详见代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; //每个矩形的数据
struct data {
int lx,rx; //该矩形最左侧的横坐标与最右侧的横坐标
int ly,ry; //纵坐标同理
}; const int maxn=, maxx=;
int n;
data a[maxn+];
int highest[maxx+]; //已搜到的最高矩形上边界的高度 bool cmp_x(data x, data y) { return x.lx<y.lx; } bool cmp_y(data x, data y) { return x.ly<y.ly; } void kuaidu(int &p) {
char c; int f=; p=;
do { c=getchar(); if (c=='-') f=-; } while (c<''||c>'');
do p=p*+c-'', c=getchar(); while (c>=''&&c<='');
p*=f;
} void init() {
kuaidu(n);
for (int i=; i<=n; i++) {
kuaidu(a[i].lx); kuaidu(a[i].ly); kuaidu(a[i].rx); kuaidu(a[i].ry);
//使所有坐标变为正数
a[i].lx+=; a[i].ly+=; a[i].rx+=; a[i].ry+=;
}
} int solve_x() {
memset(highest,-,sizeof(highest));
int ans=;
//根据下底的高度，对所有矩形排序
sort(a+,a++n,cmp_x);
for (int i=; i<=n; i++)
for (int j=a[i].ly; j<a[i].ry; j++) { //处理区间[j,j+1)
//正在处理的矩形下边界高于已经搜到过的所有矩形的最高线
//所以在这个区间中多了一个矩形，答案加上上下边的长度(2)
if (highest[j]<a[i].lx) ans+=;
//更新已搜到的矩形区间[j,j+1)的最高的线的高度
if (highest[j]<a[i].rx) highest[j]=a[i].rx;
}
return ans;
} //y轴同理
int solve_y() {
memset(highest,-,sizeof(highest));
int ans=;
sort(a+,a++n,cmp_y);
for (int i=; i<=n; i++)
for (int j=a[i].lx; j<a[i].rx; j++) {
if (highest[j]<a[i].ly) ans+=;
if (highest[j]<a[i].ry) highest[j]=a[i].ry;
}
return ans;
} int main() {
init();
printf("%d\n",solve_x()+solve_y());
return ;
}