扫描线
摆烂了 \(3++\) 月后,开始学习(复习)的第一个知识点,顺便复习下 \(markdown\)
再顺便转到博客园,不定时把博客 \(luogu->cnblogs\)
【模板】扫描线
题目描述
求 \(n\) 个四边平行于坐标轴的矩形的面积并。
输入格式
第一行一个正整数 \(n\)。
接下来 \(n\) 行每行四个非负整数 \(x_1, y_1, x_2, y_2\),表示一个矩形的四个端点坐标为 \((x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)\)。
输出格式
一行一个正整数,表示 \(n\) 个矩形的并集覆盖的总面积。
样例 #1
样例输入 #1
2
100 100 200 200
150 150 250 255
样例输出 #1
18000
提示
对于 \(20\%\) 的数据,\(1 \le n \le 1000\)。
对于 \(100\%\) 的数据,\(1 \le n \le {10}^5\),\(0 \le x_1 < x_2 \le {10}^9\),\(0 \le y_1 < y_2 \le {10}^9\)。
好吧,没啥好说的,注意一下离散化的细节问题,建树里面的 \(n\) 要带 \(tot-1\),debug了好久,恼(误
上代码
#include <cstdio>
#include <algorithm>
#include <iostream>
#define int long long
const int maxn = 1e6+10;
using namespace std;
int n,cnt = 0;
int x1,x2,y1,y2,X[maxn<<1];
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0'&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
struct Scanline{
int l,r,h;
int mark;
bool operator < (const Scanline &x)const{
return h < x.h;
}
}line[maxn << 1];
int sum[maxn<<2],len[maxn<<2];
void build(int p,int l,int r)
{
len[p] = 0;
sum[p] = 0;
if(l == r) return;
int mid = l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pushup(int p,int l,int r)
{
if(sum[p]) len[p] = X[r+1] - X[l];
else len[p] = len[p<<1]+len[p<<1|1];
}
void modify(int p,int l,int r,int L,int R,int c)
{
if(X[r+1]<=L || X[l]>=R) return;
if(L <= X[l]&&X[r+1] <= R)
{
sum[p]+=c;
pushup(p,l,r);
return;
}
int mid = l+r>>1;
modify(p<<1,l,mid,L,R,c);
modify(p<<1|1,mid+1,r,L,R,c);
pushup(p,l,r);
}
signed main()
{
n = read();
for(int i = 1;i <= n;i++)
{
x1 = read(),y1 = read(),x2 = read(),y2 = read();
//printf("%lld-%lld-%lld-%lld\n",x1,y1,x2,y2);
X[2*i-1] = x1;
X[2*i] = x2;
line[2*i-1] = (Scanline){x1,x2,y1,1};
line[2*i] = (Scanline){x1,x2,y2,-1};
}
n<<=1;
sort(line+1,line+n+1);
sort(X+1,X+n+1);
int tot = unique(X+1,X+n+1) - X - 1;
build(1,1,tot-1);
int ans = 0;
for(int i = 1;i < n;i++)
{
modify(1,1,tot-1,line[i].l,line[i].r,line[i].mark);//tot-1注意
ans += len[1]*(line[i+1].h-line[i].h);
}
printf("%lld",ans);
return 0;
}
标签:10,ch,int,le,扫描线,include
From: https://www.cnblogs.com/asdfo123/p/16887765.html