思想以及在几何问题上的应用
扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。
1
二维数点
平面上n个点(xi,yi)
回答q个询问，每个询问给定一个矩形[x1,x2]*[y1,y2],询问矩形里有多少个点
10^9 需要 离散化
1 |
2
矩形面积并
Atlantis 问题
平面上n个矩形[xi1,xi2]*[yi1,yi2] (左上角[xi1,yi1]，右下角[xi2,yi2])。
问面积并是多少？
1 |
在序列问题上的应用
3
区间不同数之和
有n个数a1,a2,…,an
有q组询问，每次给一个区间[l,r],求区间不同的数字个数之和
1 |