扫 猫 线（误）
\[\tt\large\color{cornflowerblue}{Scanningline studying note: NO.1.}
\]
\[\tt\color{gold}{2021.11.14\;\;\;Update:} \]\[自己打的矩形面积并模板↓ \]
\[\tt\color{gold}{2021.11.14\;\;\;Update:} \]\[自己打的矩形面积并模板↓ \]
#include
#define ri register int
#define MAXN 1000001
#define int long long
using namespace std;
int n,x[MAXN<<1];
int ans;
struct seg_tree{
int l,r;
int len;
int cnt;
}tr[MAXN<<2];
struct scanning{
int l,r;
int h;
int flag;
bool operator <(const scanning &a) const
{
return h>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
inline void push_up(int u)
{
if(tr[u].cnt)
tr[u].len=x[tr[u].r+1]-x[tr[u].l];
else
tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
inline void modify(int u,int l,int r,int d)
{
if(x[tr[u].l]>=r||x[tr[u].r+1]<=l)
return;
if(x[tr[u].l]>=l&&x[tr[u].r+1]<=r)
{
tr[u].cnt+=d;
push_up(u);
return;
}
int mid=tr[u].l+tr[u].r>>1;
modify(u<<1,l,r,d);
modify(u<<1|1,l,r,d);
push_up(u);
}
#define G() getchar()
template inline void r(T &x)
{
x=0;
bool flag=1;
char in=G();
while(!isdigit(in))
flag&=(in!='-'),in=G();
while(isdigit(in))
x=(x<<3)+(x<<1)+in-'0',in=G();
x*=((flag<<1)-1);
}
#define p(x) putchar(x)
inline void pu(int x)
{
if(x<0)
x=~(x-1),p('-');
if(x>9)
pu(x/10);
p(x%10+'0');
}
signed main()
{
r(n);
ri a,b,c,d;
ri cnt=0;
for(ri i=1;i<=n;i++)
{
r(a),r(c);
r(b),r(d);
x[++x[0]]=a;
x[++x[0]]=b;
sl[++cnt]={a,b,c,1};
sl[++cnt]={a,b,d,-1};
}
sort(sl+1,sl+cnt+1);
sort(x+1,x+x[0]+1);
ri leng=unique(x+1,x+x[0]+1)-x-1;
build(1,1,leng-1);
for(ri i=1;i 这下面的内容是蒯的OI-WIKI上的，而OI-WIKI是蒯的博客上的(
下面是原文的版权声明.
- 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文地址: link
-
简介
扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长等问题。
-
Atlantis 问题
在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。
\[\huge\tt\color{gold}{>>姐法/Solution} \]现在假设我们有一根线，从下往上开始扫描：
- 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
- 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
- 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 \(r+1\) 和 \(r-1\) 。
- 需要
离散化。
code on OI-WIKI:
#include
#include
#include
#define maxn 300
using namespace std;
int lazy[maxn << 3]; // 标记了这条线段出现的次数
double s[maxn << 3];
struct node1 {
double l, r;
double sum;
} cl[maxn << 3]; // 线段树
struct node2 {
double x, y1, y2;
int flag;
} p[maxn << 3]; // 坐标
//定义sort比较
bool cmp(node2 a, node2 b) { return a.x < b.x; }
//上传
void pushup(int rt) {
if (lazy[rt] > 0)
cl[rt].sum = cl[rt].r - cl[rt].l;
else
cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}
//建树
void build(int rt, int l, int r) {
if (r - l > 1) {
cl[rt].l = s[l];
cl[rt].r = s[r];
build(rt * 2, l, (l + r) / 2);
build(rt * 2 + 1, (l + r) / 2, r);
pushup(rt);
} else {
cl[rt].l = s[l];
cl[rt].r = s[r];
cl[rt].sum = 0;
}
return;
}
//更新
void update(int rt, double y1, double y2, int flag) {
if (cl[rt].l == y1 && cl[rt].r == y2) {
lazy[rt] += flag;
pushup(rt);
return;
} else {
if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
if (cl[rt * 2 + 1].l < y2)
update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
pushup(rt);
}
}
int main() {
int temp = 1, n;
double x1, y1, x2, y2, ans;
while (scanf("%d", &n) && n) {
ans = 0;
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
p[i].x = x1;
p[i].y1 = y1;
p[i].y2 = y2;
p[i].flag = 1;
p[i + n].x = x2;
p[i + n].y1 = y1;
p[i + n].y2 = y2;
p[i + n].flag = -1;
s[i + 1] = y1;
s[i + n + 1] = y2;
}
sort(s + 1, s + (2 * n + 1)); // 离散化
sort(p, p + 2 * n, cmp); // 把矩形的边的横坐标从小到大排序
build(1, 1, 2 * n); // 建树
memset(lazy, 0, sizeof(lazy));
update(1, p[0].y1, p[0].y2, p[0].flag);
for (int i = 1; i < 2 * n; i++) {
ans += (p[i].x - p[i - 1].x) * cl[1].sum;
update(1, p[i].y1, p[i].y2, p[i].flag);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans);
}
return 0;
}