USACO Picture

这一题可以说是Section 5.5中最简单的一题了。不过一开始被某人的题解吓了一跳（他是用线段树过的），所以一直不敢下手。

这题的关键在于如何确定一条边是否是周长的一部分。有一种很巧妙的办法。
我们用level[a][b]表示在某个位置上面有几个矩形，那么容易知道，当level[a][b]由0变成某个数值时， 点(a,b)一定在图像的外缘；同理，当level[a][b]由某个正数变成0时，点(a,b)也一定在图像外缘。

问题来了，上面定义的level是二维数组，然而题目的坐标范围是[-10000,10000]，显然是不可行的。进一步观察可以发现，横线和竖线的统计可以分开进行，level可以降低到一维。下面以横线为例。

建立一个struct，其中包含横线的端点（两个横坐标）、高度（一个纵坐标）以及这个横线在所在矩形的位置（用一个Bool表示，在上方为1,下方为0）。

然后，对横线按照高度从高到低排序，如果高度相同，在所在矩形上方的点排在前面（否则在会产生边界误判，导致结果增大）。

接着，初始化level全为0,从高到低开始扫描，如果是在矩形上面的边，那么让这条边两端点值之间的level都+1,如果+1后level==1,说明原来的地方没有被覆盖，而现在被覆盖了，因此tot++；类似的，当遇到在下面的边，端点内的level--，若level==0,则tot++。

对于纵线也可以采用同样的处理方法。

简单分析可知，这个算法的复杂度是O(N),在极端情况下， 两个solve一共会进行400M次操作，不过USACO并没有这么变态的测试数据。最大的数据仅耗时～0.1s，并不比用线段树处理的差。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXN 10005
05
06 typedef struct
07 {
08    int b,e,s;
09    int start;
10 }Line;
11
12 Line lx[MAXN],ly[MAXN];
13 int N;
14 int stat[30000];
15 int *level;
16 long tot = 0;
17
18 int cmp(const void *a,const void *b)
19 {
20    Line *m,*n;
21    m = (Line *)a;
22    n = (Line *)b;
23    if(m->s < n->s)    return 1;
24    if(m->s == n->s)
25    {
26        if(m->start)    return -1;
27        return 1;
28    }
29    return -1;
30 }
31
32 void init()
33 {
34    scanf("%d\n",&N);
35    int i;
36    int x1,y1,x2,y2;
37    for(i = 0;i < N;i ++)     //此处写的比较乱
38    {
39        scanf("%d%d%d%d\n",&x1,&y1,&x2,&y2);
40        lx[i].b = lx[i + N].b = x1;
41        lx[i].e = lx[i + N].e = x2;
42        lx[i].s = y1;
43        lx[i + N].s = y2;
44        ly[i].b = ly[i + N].b = y1;
45        ly[i].e = ly[i + N].e = y2;
46        ly[i].s = x1;
47        ly[i + N].s = x2;
48        ly[i].start = lx[i].start = 0;
49        ly[i + N].start = lx[i + N].start = 1;
50    }
51    qsort(lx,N * 2,sizeof(Line),cmp);
52    qsort(ly,N * 2,sizeof(Line),cmp);
53 }
54
55 void solve(Line *p)
56 {
57    int i,j;
58    memset(stat,0,sizeof(stat));
59    level = stat + 15000;
60    for(i = 0;i < 2 * N;i ++)
61    {
62        if(p[i].start)
63            for(j = p[i].b;j < p[i].e;j ++)
64            {
65                level[j] ++;
66                if(level[j] == 1)    tot ++;
67            }
68        else
69            for(j = p[i].b;j < p[i].e;j ++)
70            {
71                level[j] --;
72                if(level[j] == 0)    tot ++;
73            }
74    }
75 }
76
77 int main()
78 {
79    freopen("picture.in","r",stdin);
80    freopen("picture.out","w",stdout);
81    init();
82    solve(lx);
83    solve(ly);
84    printf("%ld\n",tot);
85    return 0;
86 }