USACO/picture

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .5中的OI题目PROB Picture的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 算法一

离散化把所有矩形离散化(就是将整个平面分成许多“竖条”或“横条”，对其操作），每个矩形都由四条边组成，分为纵边和横边。对纵边和横边分别扫描一次，以横边为例：

每个矩形的两条横边中，称下面的为始边，上面的为终边。
把每条横边以纵坐标从小到大排序，如果纵坐标相同，则应把始边排到终边之前。
依次枚举每条横边
- 如果当前边为始边，则把这条边的横向的所有点j的层数增加1，即为level[j]++。如果层数由0变为了1，则这一点一定是边缘点，总周长ans++。
- 如果当前边为终边，则把这条边的横向的所有点j的层数减少1，即为level[j]--。如果层数由1变为了0，则这一点一定是边缘点，总周长ans++。

同理按此方法扫描纵边，即可得到最后结果。

--CD 其实他和之前的window 和 rectange 差不多，采用上浮操作，记录一下原来是哪个矩形，再对应求出这块“碎片”带有多少周长，计入ans ，剪枝：若此时碎片已在原矩形中间那么exit；

[编辑] 算法二

总思路：离散+线段树 (其实就是提高level[j]++的效率。。。)

首先是离散：

显然，我们有2n条纵线和2n条横线。算法中，我们只考虑纵线，因为横线的做法同纵线的做法是相同的。离散就是将这2n条线段按照从左到右的顺序排序（也就是按照每条纵线的横坐标从小到大排序），这里需要注意一点：如果出现两个相同横坐标的纵线段，属于所在矩形左边的线段要排在属于所在矩形右边的线段的左边。（这两个线段属于不同的矩形）。开始没注意到。。结果错了。。

然后是线段树：

每个节点有6个属性：s,t,l,r,c,m，分别表示左边界、右边界、左子树、右子树、覆盖数（上文提到的level）、区间内线段总长度。
对于2n条纵线段，属于矩形左边的线段添加该线段到线段树(覆盖数+1)，属于矩形右边的线段则从线

段树中删除该线段(覆盖数-1)。做添加、删除线段的同时，要维护m属性。规则如下：

- 如果该段线段覆盖数(c)>0，则M即为线段长，
- 如果覆盖数(c)=0，则M为左儿子的M+右儿子的M。(如果本身是叶子就为0）
每次操作线段后改变总长度（也可能不变），如果原来的长度为old，新的长度为new，如果new>old，则new-old算入答案ans。

补充，如果用线段树做，还可以用另外一种更容易理解，更容易实现的方法，请见我的博客：

http://hi.baidu.com/winterlegend/blog/item/242c6809270633d863d98630.html

[编辑] 无语

线段树0.5s，暴力扫描的0.2s

[编辑] 一点算法外的话

我把C++里面的例程都看了一遍，貌似pascal的也是...发现大家读入数据的时候都好蛋疼啊，读一个数据用近10行代码...
这非常不好啊，占地方，且不易调试。其实呢问题主要是出现在类（结构体其实就是默认public的类）的赋值上
我就借这道题给尚对C++不熟悉的同学们讲一下构造函数吧。使用C++的同学们，可以在定义自己的类时候，可以重载构造函数，比如这样

struct segment//这道题的线段类
{
    int st, ed, ht;//st,ed是两个端点的坐标，ht是高度
    bool lab;//区分始边，终边
    segment(int _st = 0, int _ed = 0, int _ht = 0, bool _lab = false):
        st(_st), ed(_ed), ht(_ht), lab(_lab){ }//重载的构造函数，加了一点默认值实参
}
//读入数据
    fin >> lx >> ly >> rx >> ry;
    hor[(i<<1)-1] = segment(lx,rx,ly,true);//hor和ver数组分别记录水平的和竖直的
    hor[i<<1] = segment(lx,rx,ry,false);
    ver[(i<<1)-1] = segment(ly,ry,lx,true);
    ver[i<<1] = segment(ly,ry,rx,false);
//顺便再补充一个东西，还以上面定义的segment类为例
    segment *ptr;//声明一个指向segment类的指针
    //我们在进行动态内存分配的时候可以方便的这样做
    ptr = new segment(a,b,c,d);

这样就简单明了多啦,尤其是补充的那种用法，在写一些类似链表的东西的时候非常方便
另外还要注意自己定义了构造函数后，编译器就不提供默认构造函数了（默认构造函数简单的说就是不带任何参量的构造函数）
这样我们声明该类的变量的时候就必须使用自己的构造函数
这就为声明类的数组带来了麻烦，因为我们不可能对数组内所有的元素一个一个构造，会累死人的...
解决方法就是再定义一个默认构造函数或者像我这样把所有的实参全搞成默认的
这些只是一小部分，有兴趣的同学可以去找一些讲C++的书去看一看
其实俺这个只是语言的技巧，跟算法扯不上边，姑且放到这里吧...

c++11现在已经牛逼大了。

对于POD类型(Plain Old Datatype)，可以这样初始化，不用自定义构造函数： struct POD { int x, y, z; }; int main() { POD pod = {1, 2, 3}; return 0; }

呵呵呵呵呵呵

[编辑] 参考代码

C

C++

Pascal