二维平面有n个平行于坐标轴的矩形,现在要求出这些矩形的总面积.
输入：每个长方形左下角和右上角的坐标。
image.png
所谓扫描线，就是从下到上将图形分开，不管原来怎么重叠，现在只当作几个长方形看。如图：
image.png
具体细节：
1.离散化：
输入的两个点横坐标为小数，再线段树中需要离散化(排序，去重）
double a[maxn],b[maxn],c[maxn],d[maxn],mp[maxn*2+1];
unordered_map<double,int> _hash;
for(int i = 0 ; i < n ; i++){
scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&d[i]);
mp[k++] = a[i];
mp[k++] = c[i];
}
sort(mp,mp+k);
en = unique(mp,mp+k)-mp;
for(int i = 0 ; i < en ; i++){
_hash[mp[i]] = i+1;
}
for(int i = en ; i >= 1 ; i--){
mp[i] = mp[i-1];
}
mp[en+1] = mp[en];
2.按照h排序，即每个点的y坐标。
这里用pair，加到线段树中，入边++，出边--。
typedef pair<double,int> pi;
typedef pair<int,int> pk;
typedef pair<pi,pk> pii;
pii tr[maxn];
for(int i =0 ; i < n ; i++){
tr[i*2] = make_pair(make_pair(b[i],1),make_pair(_hash[a[i]],_hash[c[i]]));
tr[i*2+1] = make_pair(make_pair(d[i],-1),make_pair(_hash[a[i]],_hash[c[i]]));
}
sort(tr,tr+n*2);
3.线段树维护标记lz，-1为左子树右子树区间中，作为入边和出边不同的时候。>0为这个区间被覆盖，即重新划线之后这段区间是新的长方形部分。
所以push_down和push_up函数要讨论一下lz的值
void push_down(int rt,double lon1,double lon2){
if(tree[rt].lz!=-1){
tree[rt*2].lz += tree[rt].lz;
if(tree[rt*2].lz != 0)tree[rt*2].sum = lon1;
else tree[rt*2].sum = 0;
tree[rt*2+1].lz += tree[rt].lz;
if(tree[rt*2+1].lz != 0) tree[rt*2+1].sum = lon2;
else tree[rt*2+1].sum =0;
tree[rt].lz = 0;
}
}
void push_up(int rt){
if(tree[rt*2].lz == -1 || tree[rt*2+1].lz == -1)
tree[rt].lz = -1;
else if(tree[rt*2].lz != tree[rt*2+1].lz)
tree[rt].lz = -1;
else
tree[rt].lz = tree[rt*2].lz;
tree[rt].sum = tree[rt*2].sum+tree[rt*2+1].sum;
}
4.离散化之后不能单纯的sum了，因为真正的长度为mp[r]-mp[l],所以求的时候要update(l,r-1)
update函数里求sum则是
push_down(rt,mp[m+1]-mp[l],mp[r+1]-mp[m+1]);
保证最后结果是对的。
#include <unordered_map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 510;
typedef pair<double,int> pi;
typedef pair<int,int> pk;
typedef pair<pi,pk> pii;
int n,en;
pii tr[maxn];
int k;
double a[maxn],b[maxn],c[maxn],d[maxn],mp[maxn*2+1];
unordered_map<double,int> _hash;
struct node{
int lz;
double sum;
}tree[maxn*2*4+10];
void init(){
for(int i = 0 ; i < n ; i++){
scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&d[i]);
mp[k++] = a[i];
mp[k++] = c[i];
}
sort(mp,mp+k);
en = unique(mp,mp+k)-mp;
for(int i = 0 ; i < en ; i++){
_hash[mp[i]] = i+1;
//mp[i]:value of x(double)
}
for(int i = en ; i >= 1 ; i--){
mp[i] = mp[i-1];
//mp[i]:value of x(double)
}
mp[en+1] = mp[en];
for(int i =0 ; i < n ; i++){
tr[i*2] = make_pair(make_pair(b[i],1),make_pair(_hash[a[i]],_hash[c[i]]));
tr[i*2+1] = make_pair(make_pair(d[i],-1),make_pair(_hash[a[i]],_hash[c[i]]));
}
sort(tr,tr+n*2);
}
void build(int l,int r,int rt){
if(l == r){
tree[rt].lz = 0;
tree[rt].sum = 0.0;
return ;
}
int m = (l+r)/2;
build(lson);
build(rson);
tree[rt].lz = 0;
tree[rt].sum = 0.0;
}
void push_down(int rt,double lon1,double lon2){
if(tree[rt].lz!=-1){
tree[rt*2].lz += tree[rt].lz;
if(tree[rt*2].lz != 0)tree[rt*2].sum = lon1;
else tree[rt*2].sum = 0;
tree[rt*2+1].lz += tree[rt].lz;
if(tree[rt*2+1].lz != 0) tree[rt*2+1].sum = lon2;
else tree[rt*2+1].sum =0;
tree[rt].lz = 0;
}
}
void push_up(int rt){
if(tree[rt*2].lz == -1 || tree[rt*2+1].lz == -1)
tree[rt].lz = -1;
else if(tree[rt*2].lz != tree[rt*2+1].lz)
tree[rt].lz = -1;
else
tree[rt].lz = tree[rt*2].lz;
tree[rt].sum = tree[rt*2].sum+tree[rt*2+1].sum;
}
void update(int L,int R,int l,int r,int rt,int ch){
if(L <= l && r <= R){
if(tree[rt].lz != -1){
tree[rt].lz += ch;
if(tree[rt].lz != 0)tree[rt].sum = (mp[r+1]-mp[l]);
else tree[rt].sum = 0.0;
return ;
}
}
int m = (l+r)/2;
push_down(rt,mp[m+1]-mp[l],mp[r+1]-mp[m+1]);
if(L <= m) update(L,R,lson,ch);s
if(R > m) update(L,R,rson,ch);
push_up(rt);
}
void sov(){
double ans = 0;
build(1,en,1);
for(int i = 0 ; i < n*2-1 ; i++){
double h = tr[i].first.first;
update(tr[i].second.first,tr[i].second.second-1,1,en,1,tr[i].first.second);
ans += tree[1].sum*(tr[i+1].first.first-h);
}
printf("%.2lf\n\n",ans);
}
int main(){
int T = 1;
while(scanf("%d",&n)!= EOF && n){
init();
printf("Test case #%d\nTotal explored area: ",T);
sov();
T++;
}
}
