二維平面有n個(gè)平行于坐標(biāo)軸的矩形,現(xiàn)在要求出這些矩形的總面積.
輸入：每個(gè)長方形左下角和右上角的坐標(biāo)。
image.png
所謂掃描線龟梦，就是從下到上將圖形分開，不管原來怎么重疊窃躲，現(xiàn)在只當(dāng)作幾個(gè)長方形看计贰。如圖：
image.png
具體細(xì)節(jié)：
1.離散化：
輸入的兩個(gè)點(diǎn)橫坐標(biāo)為小數(shù)，再線段樹中需要離散化(排序蒂窒，去重）
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排序躁倒，即每個(gè)點(diǎn)的y坐標(biāo)。
這里用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.線段樹維護(hù)標(biāo)記lz象迎，-1為左子樹右子樹區(qū)間中，作為入邊和出邊不同的時(shí)候停士。>0為這個(gè)區(qū)間被覆蓋挖帘，即重新劃線之后這段區(qū)間是新的長方形部分。
所以push_down和push_up函數(shù)要討論一下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了恋技，因?yàn)檎嬲拈L度為mp[r]-mp[l],所以求的時(shí)候要update(l,r-1)
update函數(shù)里求sum則是
push_down(rt,mp[m+1]-mp[l],mp[r+1]-mp[m+1]);
保證最后結(jié)果是對的拇舀。
#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++;
}
}
