扫描线专题
洛谷P5490扫描线
0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去
Zxing扫描二维码精简(竖屏、拉伸处理、扫描框大小和扫描线移动、开灯）
自己在简版zxing的基础上美化了下，给大家分享下，直接扫描功能没问题。 就是从相册导入图片，解码一直不成功，导入图片解码 我引入了一个解码类 RGBLuminanceSource（百度网上二维码图片解码都是这个，我还把这个类编译了，导到core.jar包里面了）， 好像是hity类型有问题，反正一直不成功。 有大神解决了，回复告诉我！谢谢！ 分享 暂时没做效
扫描线Sweep Line算法总结
扫描线算法，推荐还是用标准的模板去写，treemap只适合于求最大的overlap个数的题目，其余的不能用treemap来解，所以推荐还是用event的思想去+1, -1然后排序扫描的方法可以用来解所有的题型； Number of Airplanes in the Sky 思路：经典扫描线算法：把interval起飞和降落做为event，全部打散，按照时间排列，同时时间相等的，按照降落在前面，起
矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）
转自：http://blog.csdn.net/lwt36/article/details/48908031 HDU 1542 [POJ 1151] Atlantis （矩形面积并） 题意: 求N<=100个矩形的面积并 分析: 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化 x 坐标就可以了扫描线: 首先把矩形按 y 轴分成两条边, 上边和下边,
【HDU1255】【线段树】【扫描线】【面积】
覆盖的面积 Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4417 Accepted Submission(s): 2180 Problem Description 给定平面上若干矩形,求出被这些矩形覆
poj2482--Stars in Your Window(扫描线)
题目链接：点击打开链接 链接题目大意：给出n个星星的坐标，每个星星有一个亮度，给出一个矩形的长和宽，问矩形能包括的星星的最大亮度和（不包括边框）。 假设每个星星都是矩形的最左下点，那么每一个星星都可以得到一个矩形，(x,y)->(x,y,x+w,y+h)，这个矩形的两条高边的值也就是星星的亮度k和-k，对于不同的矩形来说，如果高线出现重合部分，那么也就是说这两个星是可以出现在同一个矩形中的，扫
HDU 1828 POJ 1177 Picture(线段树+扫描线+离散化）
HDU题目地址：HDU 1828 POJ题目地址：POJ 1177 这题是求周长并，我用的方法可能有点麻烦。。是先求横着的线，再求竖着的线。每次只要求出每次的总区间覆盖长度，然后每次累加这次的总区间覆盖与上次的总区间覆盖长度的差的绝对值。因为只有长度发生变化时，才会产生一段新的周长。 待会再试试只扫描一次的方法。此博客有待更新。 代码如下： #include <iostream>#
POJ 3277 City Horizon(线段树+扫描线+离散化）
题目地址：POJ 3277 水题。。稍微处理一下然后用求面积并的方法求即可。 代码如下： #include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#
HDU 1542 POJ 1151 Atlantis(线段树+扫描线）
题目地址：HDOJ地址：HDU 1542 POJ 地址：POJ 1151 第一发扫描线。。费了好大一番功夫。。构思用了半天。。写出来调试成功用了半天。。。真是弱渣。。 所谓扫描线就是从上往下或从下往上扫描，每到一个边，就进行增或删的处理。最后出来的值就是总的面积。对于求面积并的问题，可以参考这篇博客（博客地址），讲的不错。 具体实现过程是用lazy标记此时的边数量，如果大于0，说明这个地方
Atlantis 线段树扫描线--面积并
Atlantis Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 16755 Accepted: 6391 Description There are several ancient Greek texts that contain descript
线段树算法 ---- 扫描线之面积并
一、扫描线算法 基本思想 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 对于一条扫描线填充过程可以分为四个步骤： (1) 求交：计算扫描线与多边形各边的交点 (2) 排序：把所有交点按 x 坐标递增顺序来排序 (3) 配对：确定扫描线与多边形的相交区间，第一个与第二个，第三个与第四个等等，每对交点代
POJ 1177 Picture (线段树扫描线)
题意： 给定n个矩形（0 <= n < 5000）的左下角坐标(x1,y1)和右上角坐标(x2,y2) (-10000 <= x1,x2,y1,y2 <= 10000) 求所有矩形重合后的图形的周长，如下图（图片来自POJ 1177）： 做法：线段树扫描线。 由于值域不大，所以不需要离散化，直接将Y值向正方向平移10001个单位，然后用线段树直接做。 扫描线就是用垂直于x轴的线
POJ 2482 Stars in Your Window (线段树扫描线)
题意： 给定n个星星的坐标(x,y)以及亮度c ,求用一个宽W,高H的框（不含边界），能框住的星星的亮度总和的最大值为多少。 ( 0<= x,y <2^31 , 1<=c<=100 , 1<=W , H <= 1000000 , x,y,c,W,H都是整数) 思路： 用矩形右上角坐标（X,Y）来代表矩形位置，原问题等价于，X,Y为整数，用一个宽W,高H的框（不含左，下
FZU 2187 扫描线
和HDU 1255差不多 这次是求只被覆盖一次的矩形面积和 修改callen函数即可 data[k].len表示被覆盖的纵长度 data[k].key表示被只被覆盖一次的纵长度 #include "stdio.h"#include "string.h"#include "stdlib.h"#include "math.h"#include "iostream"#inc
HDU 1255 扫描线
扫描线处理矩形覆盖过至少两次的区域的面积. 把callen函数的修改一下即可 data[k].len表示被覆盖的长度 data[k].sum表示被覆盖两次以上的长度 #include "stdio.h"#include "string.h"#include "algorithm"#include "math.h"using namespace std;struct Mar
poj1177--Picture--扫描线
思想和前段时间的1151差不多， 都是通过扫描线的移动来计算周长，不同的是要通过对与x轴平行的扫描线扫一次，与y轴平行的扫描线扫一次， 扫描两次得到周长。 变量last为记录上一次扫描得到的长度，sum为记录这一次总共扫描得到的长度。 abs(sum-last)即为所扫描到的一次长度， 非常耐人寻味的是，我询问学长为什么可以这样做的时候，学长提到了一个投影的
P5490.扫描线（python）
这个洛谷怎么对于python不太友好呢，没几次能全过的 本题使用扫描线的模板，首先把所有x坐标排序去重，放进列表X中。把所有横线lines排序。这样把所有矩阵都分成了块。对于每一块，高=lines[i+1]-lines[i]，宽就等于在这一块中，每个矩阵的并。 比如说图中，纵坐标在3-5之间，那么高度就是2，其中有两块矩阵并起来，计算并起来的宽度=80-10=70，高×宽就是这一块的面积。
CSU 1335: 高桥和低桥(扫描线) 13年省赛题
1335: 高桥和低桥 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 957 Solved: 279 [ Submit][ Status][ Web Board] Description 有个脑筋急转弯是这样的：有距离很近的一高一低两座桥，两次洪水之后高桥被淹了两次，低桥却只被淹了一次，为什么？答案是：因为低桥太低了，第一次洪
Snowy Smile HDU - 6638（扫描线，线段树区间合并）
There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest’s location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the c
js实现扫描线填色算法使用canvas展示
算法原理 扫描线填色算法的基本思想是：用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。 效果 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8">
线段树，扫描线详解（非常详细）
目录 一：综述 二：原理 (1)线段树的点修改： (2)线段树的区间查询： (3)线段树的区间修改： (4)线段树的存储结构： 三：递归实现 四：非递归原理 点修改： 点修改下的区间查询： 区间修改下的区间查询： 区间修改： 五：非递归实现 六：线段树解题模型 （1）：字符串哈希 （2）：最长连续零 （3）：计数排序 （4）总结： 七：扫描线 扫描线求重叠矩
JZOJ 1495. 宝石（附加扫描线讲解）
JZOJ 1495. 宝石 题目大意：给你N个 ( K + 1 ) × ( K + 1 ) (K+1)\times(K+1) (K+1)×(K+1)的正方形以及他们左上角的那个顶点的坐标和它的权值，求最大的覆盖的权值。 这一题可以用二维前缀和做，但是无法拿到满分。 满分做法：扫描线。 假如现在有这么两个长方形，权值都为1（不要问为什么是长方形，这里只是为了方便讲解而已），它们摆放如图： 首
线段树(扫描线法，单点修改区间查询
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 200010;int m, p;struct Node{int l, r;int v; // 区间[l, r]中的最大值}tr[N * 4];void pushup(