线段树辅助——扫描线法计算矩形周长并(轮廓线)
例题:hdu 1828 Picture有两种方法,不过常用的第二种,两种都说一下。第一种:把矩形分成横线和竖线去处理,可知是完全相同的操作,我们来讲下怎么算出横线部分,竖线部分就是照搬即可。将横线保存在一个表中,按横线所处的竖直位置排序(升序),另外每条横线带一个标记值,原矩形的下线为1,上线为-1(对应过去就是插入线段和删除线段)从低到高扫描横线,没扫到一条横线就能计算出一部...