[模板] 扫描线

一、扫描线求矩形面积并

如图所示总矩形面积并等于每两根蓝线间的面积和。

考虑将矩形按x轴排序，只需要知道每个离散的x点上被矩形覆盖的长度 $line$ ，和下一条扫描线的x轴可知之间面积为 $line * (arr[j].x - arr[i].x)$

所以只需要维护每一条扫描线的长度即可，线段树 $O(Nlogn)$ 暴力维护 $O(n^2)$

题目链接 https://vjudge.net/problem/POJ-1151

线段树维护

const int MAXN = 1e6 + 10;
int tf = 0, rf = 0;

struct rec
{
	ld a, b, c, d;
}pot[MAXN] = {0};

struct node
{
	ld x;
	int y1, y2, ok;
	node(){}
	node(ld a, int b, int c, int d)
	{ x = a, y1 = b, y2 = c, ok = d; }
}arr[MAXN];

bool cmp(node a, node b)
{
	if(a.x != b.x)
		return a.x < b.x;
	else return a.ok > b.ok;
}

struct sgt
{
	int l, r, cnt; //节点l = r = 1 代表以1开头2结尾的段的扫描长度 l = 1, r = 2代表1开头3结尾的段的扫描长度 
	double len; //cnt代表当前段内的标记次数， 若大于1则不用下探 
}t[MAXN << 2];

ld vy[MAXN] = {0};
int ret(ld x) { return lower_bound(vy, vy + tf, x) - vy + 1; } //树是从1开始建的， 离散也从1离散 
double raw(int x) {return vy[x - 1]; }

void build(int now, int l, int r)
{
	t[now].l = l, t[now].r = r;
	t[now].len = 0, t[now].cnt = 0;
	if(l == r) return ;
	int mid = (l + r) / 2;
	build(now * 2, l, mid);
	build(now * 2 + 1, mid + 1, r);
}

void push(int now)
{
	if(t[now].cnt) //如果当前段被完全覆盖 则长度为len(r + 1) - len(l) 
		t[now].len = raw(t[now].r + 1) - raw( t[now].l);
	else //否则合并 
		t[now].len = t[now * 2].len + t[now * 2 + 1].len;
}

void change(int now, int l, int r, int v)
{
	if(t[now].l >= l && t[now].r <= r) 
	{	
		t[now].cnt += v; //完全包含的段直接标记即可 
		push(now);
		return ;
	}
	int mid = (t[now].l + t[now].r) / 2;
	if(l <= mid) change(now * 2, l, r, v);
	if(r > mid) change(now * 2 + 1, l, r, v);
	push(now);
}

int main()
{ 
	int n, ttt = 1;

	while(scanf("%d", &n) && n)
	{
		tf = 0, rf = 0;
		fr(i, 0, n)
		{ 
			scanf("%lf%lf%lf%lf", &pot[i].a, &pot[i].b, &pot[i].c, &pot[i].d);
			vy[tf++] = pot[i].b; vy[tf++] = pot[i].d;
		}
		
		sort(vy, vy + tf); //离散所有y值 
		tf = unique(vy, vy + tf) - vy;
		
		fr(i, 0, n) //对所有左右边建权，左边1 右边-1 
		{
			arr[rf++] = node( pot[i].a, ret(pot[i].b), ret(pot[i].d), 1 ); 
			arr[rf++] = node( pot[i].c, ret(pot[i].b), ret(pot[i].d), -1 );
		}
		
		sort(arr, arr + rf, cmp); //对所有左右边按x值递增排序
		
		build(1, 1, tf - 1);
		 
		ld ans = 0.0;
		
		for(int i = 0; i < rf;)
		{
			int j = i;
			while(j < rf && arr[j].x == arr[i].x) //找到一段x值相同的边并暴力合并 
				change(1, arr[j].y1, arr[j].y2 - 1, arr[j].ok), ++j;
			if(j != rf)	ans += (t[1].len * (arr[j].x - arr[i].x)); //计算当前扫描线(已经更新在t[1].len了)和下一个x值
			i = j;
		}
		printf("Test case #%d
", ttt++);
		printf("Total explored area: %.2f
", ans);
		printf("
"); 
	}

    return 0;
}

暴力维护

int tf = 0, rf = 0;

struct rec
{
	ld a, b, c, d;
}pot[MAXN] = {0};

struct node
{
	ld x;
	int y1, y2, ok;
	node(){}
	node(ld a, int b, int c, int d)
	{ x = a, y1 = b, y2 = c, ok = d; }
}arr[MAXN];

bool cmp(node a, node b)
{
	if(a.x != b.x)
		return a.x < b.x;
	else return a.ok < b.ok;
}

int used[MAXN] = {0}; //记录当前段在矩形内出现次数 
ld vy[MAXN] = {0};
int ret(ld x) { return lower_bound(vy, vy + tf, x) - vy; }

void opt(node x)
{
	if(x.ok == -1) fr(i, x.y1, x.y2) --used[i];
	else fr(i, x.y1, x.y2) ++used[i];
}

ld cal()
{
	ld sum = 0.0;
	fr(i, 0, tf) if(used[i]) sum += (vy[i + 1] - vy[i]);
	return sum;
}

int main()
{ 
	int n, ttt = 1;

	while(scanf("%d", &n) && n)
	{
		memset(used, 0, sizeof(used));
		tf = 0, rf = 0;
		fr(i, 0, n)
		{ 
			scanf("%lf%lf%lf%lf", &pot[i].a, &pot[i].b, &pot[i].c, &pot[i].d);
			vy[tf++] = pot[i].b; vy[tf++] = pot[i].d;
		}
		sort(vy, vy + tf); //离散所有y值 
		tf = unique(vy, vy + tf) - vy;
		fr(i, 0, n) //对所有左右边建权，左边1 右边-1 
		{
			arr[rf++] = node( pot[i].a, ret(pot[i].b), ret(pot[i].d), 1 ); 
			arr[rf++] = node( pot[i].c, ret(pot[i].b), ret(pot[i].d), -1 );
		}
		sort(arr, arr + rf, cmp); //对所有左右边按x值递增排序 
		ld ans = 0.0;
		for(int i = 0; i < rf;)
		{
			int j = i;
			while(j < rf && arr[j].x == arr[i].x) //找到一段x值相同的边并暴力合并 
				opt(arr[j]), ++j;
			if(j != rf)	ans += (cal() * (arr[j].x - arr[i].x)); //计算当前扫描线和下一个x值
			i = j;
		}
		printf("Test case #%d
", ttt++);
		printf("Total explored area: %.2f
", ans);
		printf("
"); 
	}

    return 0;
}

二、扫描线求边长为k的矩形覆盖最大点数

题目链接：https://cometoj.com/contest/59/problem/D?problem_id=2713

思路，将每个点变成左下角 $x,y$ 右上角 $x + k, y + k$ 的矩形，若两个矩形有交点，则证明在交点这个地方框一个 $k*k$ 的矩形必然可以覆盖这两个点。则最大矩形覆盖就是交点个数最多的点。

扔按上面矩形面积并跑扫描线，先加边后删边（因为边缘可以覆盖，则当前x值不删边时答案更优）

将y轴离散为点，线段树区间lazy加和求极值即为答案。

对于样例

4 2
1 1
3 1
3 4
2 2 有下图更新方式

代码：

/*
    Zeolim - An AC a day keeps the bug away
*/
 
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h> 
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 386910137;
const ull P = 13331; 
const int MAXN = 1e6 + 10;
int tf = 0, rf = 0;

struct rec
{
	ld a, b, c, d;
}pot[MAXN] = {0};

struct node
{
	ld x;
	int y1, y2, ok;
	node(){}
	node(ld a, int b, int c, int d)
	{ x = a, y1 = b, y2 = c, ok = d; }
}arr[MAXN];

bool cmp(node a, node b)
{
	if(a.x != b.x)
		return a.x < b.x;
	else return a.ok > b.ok;
}

struct sgt
{
	int l, r, cnt, add, max; //½Úµãl = r ´ú±íµ±Ç°É¨ÃèÏßÉÏµãl³öÏÖµÄ´ÎÊý
	#define ls(x) t[now * 2]
	#define rs(x) t[now * 2 + 1]
}t[MAXN << 2];

int vy[MAXN] = {0};
int ret(ld x) { return lower_bound(vy, vy + tf, x) - vy + 1; } //Ê÷ÊÇ´Ó1¿ªÊ¼½¨µÄ£¬ ÀëÉ¢Ò²´Ó1ÀëÉ¢ 
double raw(int x) {return vy[x - 1]; }

void build(int now, int l, int r)
{
	t[now].l = l, t[now].r = r;
	t[now].cnt = t[now].add = t[now].max = 0;
	if(l == r) return ;
	int mid = (l + r) / 2;
	build(now * 2, l, mid);
	build(now * 2 + 1, mid + 1, r);
}

void push(int now) //ÏÂÍÆlazy
{
	if(t[now].add)
	{
		ls(now).max += t[now].add;
		rs(now).max += t[now].add;
		ls(now).add += t[now].add;
		rs(now).add += t[now].add;
		t[now].add = 0;
	}
}

void change(int now, int l, int r, int v)
{
	if(t[now].l >= l && t[now].r <= r)  //Î¬»¤Çø¼ä×î´óÖµ 
	{	
		t[now].max += v; //ÍêÈ«°üº¬µÄ¶ÎÖ±½Ó¼ÆËã+lazy 
		t[now].add += v;  
		return ;
	}
	push(now);
	int mid = (t[now].l + t[now].r) / 2;
	if(l <= mid) change(now * 2, l, r, v);
	if(r > mid) change(now * 2 + 1, l, r, v);
	t[now].max = max(ls(now).max, rs(now).max);
}

int main()
{ 
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, k, ttt = 1;

	cin >> n >> k;

	tf = 0, rf = 0;
	fr(i, 0, n)
	{ 
		cin >> pot[i].a >> pot[i].b;
		pot[i].c = pot[i].a + k;
		pot[i].d = pot[i].b + k;
		vy[tf++] = pot[i].b; vy[tf++] = pot[i].d;
	}
	
	sort(vy, vy + tf); //ÀëÉ¢ËùÓÐyÖµ 
	tf = unique(vy, vy + tf) - vy;
	
	fr(i, 0, n) //¶ÔËùÓÐ×óÓÒ±ß½¨È¨£¬×ó±ß1 ÓÒ±ß-1 
	{
		arr[rf++] = node( pot[i].a, ret(pot[i].b), ret(pot[i].d), 1 ); 
		arr[rf++] = node( pot[i].c, ret(pot[i].b), ret(pot[i].d), -1 );
	}
	
	sort(arr, arr + rf, cmp); //¶ÔËùÓÐ×óÓÒ±ß°´xÖµµÝÔöÅÅÐò
	
	build(1, 1, tf);
	 
	int ans = 0;
	
	for(int i = 0; i < rf; ++i)
	{
			change(1, arr[i].y1, arr[i].y2, arr[i].ok);
		ans = max(ans, t[1].max ); //¼ÆËãµ±Ç°É¨ÃèÏßÄÚ×î´óµã¸²¸ÇÊý 
	}
	
	cout << ans << '
';

    return 0;
}

/*
4
10 10 20 20
15 15 30 25
25 10 35 20
25 25 35 30
*/