icontofig | 发布于 2019-03-12 17:13:37 | 阅读量 367 | 线段树 扫描线

# 题解

（图来自于别人的博客，实在是不想自己画图了QAQ）

1.当前区间表示的线段被完全覆盖：区间被覆盖的线段总长即为这段区间表示的线段总长。

2.当前区间表示的线段未被完全覆盖：当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
double x1, x2, y1, y2; int id;
node(double X1 = 0, double Y1 = 0, double X2 = 0, double Y2 = 0) { x1 = X1, y1 = Y1, x2 = X2, y2 = Y2; }
}p[maxn], x[maxn];

struct node2{
int x1, x2, k; double h;
node2(int X1 = 0, int X2 = 0, double H = 0, int K = 0) : x1(X1),x2(X2),h(H),k(K){};
}nod[maxn];
bool cmp(node a,node b){
return a.x1 < b.x1;
}
bool cmp2(node2 a,node2 b){
return a.h < b.h;
}
struct tree{
int vis,l,r;
double sum;
}tr[maxn<<2];
int n,cnt,tot;
double pid[maxn<<1];
double a,b,c,d;
void build(int now,int l,int r){
tr[now].l = l;
tr[now].r = r;
tr[now].sum = tr[now].vis = 0;
if(l == r)
return;
int mid = (l + r) >> 1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
return;
}
void push_up(int now){
if(tr[now].vis)
tr[now].sum = pid[tr[now].r+1] - pid[tr[now].l];
else
tr[now].sum = tr[now<<1].sum + tr[now<<1|1].sum;
return;
}
void update(int now,int l,int r,int k){
if(tr[now].l >= l && tr[now].r <= r){
tr[now].vis += k;
push_up(now);
return;
}
int mid = (tr[now].r + tr[now].l) >> 1;
if(l <= mid)update(now<<1,l,r,k);
if(r > mid)update(now<<1|1,l,r,k);
push_up(now);
return;
}
int cas = 0;
double ans;
int main(){
while(scanf("%d",&n) && n != 0){
cas++;
ans = 0;
tot = 2 * n;
memset(tr,0,sizeof(tr));
cnt = 0;
for(int i = 1;i <= n;++i){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
p[i] = node(a,b,c,d);
x[i] = node(a,0,0,0);
x[i+n] = node(c,0,1,0);
x[i].id = x[i+n].id = i;
}
sort(x+1,x+1+tot,cmp);
x[0].x1 = -1;
for(int i = 1;i <= tot;++i){
if(x[i].x1 != x[i-1].x1)pid[++cnt] = x[i].x1;
if(!x[i].x2)p[x[i].id].x1 = cnt;
else p[x[i].id].x2 = cnt;
}
build(1,1,cnt);
for(int i = 1;i <= n;++i){
nod[i] = node2(p[i].x1,p[i].x2,p[i].y1,1);
nod[i+n] = node2(p[i].x1,p[i].x2,p[i].y2,-1);
}
sort(nod+1,nod+tot+1,cmp2);
for(int i = 1;i <= tot;++i){
if(i != 1)ans += (nod[i].h - nod[i-1].h) * tr[1].sum;
update(1,nod[i].x1,nod[i].x2-1,nod[i].k);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas,ans);
}
return 0;
}﻿   ```

367 人读过

0 条评论