题目描述

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)。

详见代码：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 //每个矩形的数据
 7 struct data {
 8     int lx,rx; //该矩形最左侧的横坐标与最右侧的横坐标
 9     int ly,ry; //纵坐标同理
10 };
11 
12 const int maxn=5000, maxx=20000;
13 int n;
14 data a[maxn+1]; 
15 int highest[maxx+1]; //已搜到的最高矩形上边界的高度 
16 
17 bool cmp_x(data x, data y) { return x.lx<y.lx; }
18 
19 bool cmp_y(data x, data y) { return x.ly<y.ly; }
20 
21 void kuaidu(int &p) {
22     char c; int f=1; p=0;
23     do { c=getchar(); if (c=='-') f=-1; } while (c<'0'||c>'9');
24     do p=p*10+c-'0', c=getchar(); while (c>='0'&&c<='9');
25     p*=f;
26 }
27 
28 void init() {
29     kuaidu(n);
30     for (int i=1; i<=n; i++) {
31         kuaidu(a[i].lx); kuaidu(a[i].ly); kuaidu(a[i].rx); kuaidu(a[i].ry);
32         //使所有坐标变为正数
33         a[i].lx+=10001; a[i].ly+=10001; a[i].rx+=10001; a[i].ry+=10001;
34     }
35 }
36 
37 int solve_x() {
38     memset(highest,-1,sizeof(highest));
39     int ans=0;
40     //根据下底的高度，对所有矩形排序
41     sort(a+1,a+1+n,cmp_x);
42     for (int i=1; i<=n; i++)
43         for (int j=a[i].ly; j<a[i].ry; j++) { //处理区间[j,j+1)
44             //正在处理的矩形下边界高于已经搜到过的所有矩形的最高线
45             //所以在这个区间中多了一个矩形，答案加上上下边的长度(2)
46             if (highest[j]<a[i].lx) ans+=2;
47             //更新已搜到的矩形区间[j,j+1)的最高的线的高度
48             if (highest[j]<a[i].rx) highest[j]=a[i].rx;
49         }
50     return ans;
51 }
52 
53 //y轴同理
54 int solve_y() {
55     memset(highest,-1,sizeof(highest));
56     int ans=0;
57     sort(a+1,a+1+n,cmp_y);
58     for (int i=1; i<=n; i++)
59         for (int j=a[i].lx; j<a[i].rx; j++) {
60             if (highest[j]<a[i].ly) ans+=2;
61             if (highest[j]<a[i].ry) highest[j]=a[i].ry;
62         }
63     return ans;
64 }
65 
66 int main() {
67     init();
68     printf("%d\n",solve_x()+solve_y());
69     return 0;
70 }