参考：http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html
分析:
1.矩形比较多，坐标也很大，所以横坐标需要离散化（纵坐标不需要），熟悉离散化后这个步骤不难，所以这里不详细讲解了，不明白的还请百度
2.重点：扫描线法：假想有一条扫描线，从左往右（从右往左），或者从下往上（从上往下）扫描过整个多边形（或者说畸形。。多个矩形叠加后的那个图形）。如果是竖直方向上扫描，则是离散化横坐标，如果是水平方向上扫描，则是离散化纵坐标。下面的分析都是离散化横坐标的，并且从下往上扫描的。
扫描之前还需要做一个工作，就是保存好所有矩形的上下边，并且按照它们所处的高度进行排序，另外如果是上边我们给他一个值-1，下边给他一个值1，我们用一个结构体来保存所有的上下边
struct segment
{
double l,r,h; //l，r表示这条上下边的左右坐标，h是这条边所处的高度
int f; //所赋的值，1或-1
}
接着扫描线从下往上扫描，每遇到一条上下边就停下来，将这条线段投影到总区间上（总区间就是整个多边形横跨的长度），这个投影对应的其实是个插入和删除线段操作。还记得给他们赋的值1或-1吗，下边是1，扫描到下边的话相当于往总区间插入一条线段，上边-1，扫描到上边相当于在总区间删除一条线段（如果说插入删除比较抽象，那么就直白说，扫描到下边，投影到总区间，对应的那一段的值都要增1，扫描到上边对应的那一段的值都要减1，如果总区间某一段的值为0，说明其实没有线段覆盖到它，为正数则有，那会不会为负数呢？是不可能的，可以自己思考一下）。
每扫描到一条上下边后并投影到总区间后，就判断总区间现在被覆盖的总长度，然后用下一条边的高度减去当前这条边的高度，乘上总区间被覆盖的长度，就能得到一块面积，并依此做下去，就能得到最后的面积
（这个过程其实一点都不难，只是看文字较难体会，建议纸上画图，一画即可明白，下面献上一图希望有帮组）
1.区间的并
上面已经说的很详细了，代码如下：
//Accepted 1542 15MS 316K 2539 B C++
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 400
struct node1
{
double x1,x2,h;
int d;
bool operator<(const node1 &a) const{return h<a.h;}
}line[MAXN];
double g[MAXN];
/**线段树**/
struct node2
{
int left,right,cover;
double len;
}tree[MAXN*3];
void creat(int root,int left,int right)
{
tree[root].cover=0;
tree[root].len=0;
tree[root].left=left;
tree[root].right=right;
if(right==left+1)
return ;
int mid=(right+left)>>1;
creat(2*root,left,mid);
creat(2*root+1,mid,right);
}
void upmark(int root)
{
if(tree[root].cover)
{
tree[root].len=g[tree[root].right]-g[tree[root].left];
}
else if(tree[root].left+1==tree[root].right)
tree[root].len=0;
else
tree[root].len=tree[2*root].len+tree[2*root+1].len;
}
void updata(int root,int left,int right,int d)
{
if(tree[root].left>=left&&tree[root].right<=right)
{
tree[root].cover+=d;
upmark(root);
return;
}
if(tree[root].left>right||tree[root].right<left) return ;
updata(2*root,left,right,d);
updata(2*root+1,left,right,d);
upmark(root);
}
/**线段树**/
int X;
int find(double key)
{
int l=0,r=X+1,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(g[mid]<key) l=mid+1;
else if(g[mid]>key) r=mid-1;
else return mid;
}
return 0;
}
int main()
{
int n;
int kase=1;
while(~scanf("%d",&n)&&n)
{
int num=0;
double x1,x2,y1,y2;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[num].x1=x1;
line[num].x2=x2;
line[num].h=y1;
line[num].d=1;
g[num]=x1;
num++;
line[num].x1=x1;
line[num].x2=x2;
line[num].h=y2;
line[num].d=-1;
g[num]=x2;
num++;
}
sort(g,g+num);
X=unique(g,g+num)-g;
X--;
sort(line,line+num);
creat(1,0,X);
double ans=0;
for(int i=0;i<num-1;i++)
{
int l=find(line[i].x1);
int r=find(line[i].x2);
updata(1,l,r,line[i].d);
ans+=tree[1].len*(line[i+1].h-line[i].h);
}
printf("Test case #%d\n",kase++);
printf("Total explored area: %0.2lf\n\n",ans);
}
return 0;
}
2.矩形的交
只需要注意下更新就可以了。其它基本与 区间的并一样；
1. 要有两个域：once（被覆盖一次的长度） ， len （被覆盖两次以上的长度）
2. 更新时 分三种情况： 1.该区间被覆盖2次以上，那么直接算出整个区间长就行，和区间并一样。
2. 该区间只被覆盖一次 分两种情况： 1：是叶子节点：len=0，once就是整个区间长。
2：不是叶子节点：len=左右子树的被覆盖两次和一次的和。（子树被覆盖一次+该区间一次就有两次了，所以要加上子树被覆盖一次的。）once=整个区间-len
3. 该区间被覆盖 0 次 分两种情况：1.叶子节点：len = once = 0
2.不是叶子节点：len = 左右子树 len 之和。 once = 左右子树 once 之和。
参考别人的代码：值得学习。。
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")
using namespace std;
const int MAX = 2010;
struct Tnode{int l,r,cover;double once,len;};
Tnode node[MAX<<2];
struct Sline{double x,y1,y2;int flag;};
Sline l[MAX];
double y[MAX];
void add_line(double x1,double y1,double x2,double y2,int &cnt)
{
l[cnt].x = x1; l[cnt].y1 = y1; l[cnt].y2 = y2;
l[cnt].flag = 1;
y[cnt++] = y1;
l[cnt].x = x2; l[cnt].y1 = y1; l[cnt].y2 = y2;
l[cnt].flag = -1;
y[cnt++] = y2;
}
bool cmp(Sline a,Sline b)
{
if( a.x == b.x ) return a.flag > b.flag;
return a.x < b.x;
}
void init()
{
memset(node,0,sizeof(node));
}
void Build(int t,int l,int r)
{
node[t].l = l; node[t].r = r;
node[t].cover = 0; node[t].once = 0.0;
if( node[t].l == node[t].r - 1 )
return ;
int mid = MID(l,r);
Build(L(t),l,mid);
Build(R(t),mid,r);
}
void Updata_len(int t) // 重要理解！！
{
if( node[t].cover >= 2 )
{
node[t].once = 0;
node[t].len = y[node[t].r] - y[node[t].l];
return ;
}
if( node[t].cover == 1 )
{
if( node[t].l == node[t].r - 1 )
node[t].len = 0;
else
node[t].len = node[R(t)].len + node[L(t)].len + node[R(t)].once + node[L(t)].once;
node[t].once = y[node[t].r] - y[node[t].l] - node[t].len;
return ;
}
if( node[t].cover == 0 )
{
if( node[t].l == node[t].r - 1 )
node[t].len = node[t].once = 0;
else
{
node[t].len = node[R(t)].len + node[L(t)].len;
node[t].once = node[R(t)].once + node[L(t)].once;
}
return ;
}
}
void Updata(int t, Sline p)
{
if( y[node[t].l] >= p.y1 && y[node[t].r] <= p.y2 )
{
node[t].cover += p.flag;
Updata_len(t);
return ;
}
if( node[t].l == node[t].r - 1 ) return ;
int mid = MID(node[t].l,node[t].r);
if( p.y1 <= y[mid] )
Updata(L(t),p);
if( p.y2 > y[mid] )
Updata(R(t),p);
Updata_len(t);
}
void solve(int n,int cnt)
{
init();
Build(1,0,cnt-1);
double ans = 0.0;
Updata(1,l[0]);
for(int i=1; i<n; i++)
{
ans += node[1].len*(l[i].x - l[i-1].x);
Updata(1,l[i]);
}
printf("%.2lf\n",ans);
}
int main()
{
int ncases,n;
double x1,x2,y1,y2;
scanf("%d",&ncases);
while( ncases-- )
{
scanf("%d",&n);
int cnt = 0;
for(int i=0; i<n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
add_line(x1,y1,x2,y2,cnt);
}
sort(y,y+cnt);
sort(l,l+cnt,cmp);
int t = unique(y,y+cnt) - y;
solve(cnt,t);
}
return 0;
}
3.求覆盖周长
这里在 扫描线的同时 要加上两边的值。
有三个更新：
1. cover 依然和前面一样，遇到下边就+1，遇到上边就-1；
2. m 是覆盖的边长。
3. line 是该区间有多少条边被覆盖，用来加上两个侧边。
4。 lc ，rc 用来判断端点 是否被覆盖，覆盖了就要减去一条重复的边。
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 20000
struct node1
{
int x1,x2,d,h;
bool operator<(const node1 &a) const
{
if(h!=a.h) return h<a.h;
else return d>a.d;
}
}s[MAXN];
int line[MAXN];
int num;
void read_line()
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
s[num].x1=x1;
s[num].x2=x2;
s[num].h=y1;
s[num].d=1;
line[num]=x1;
num++;
s[num].x1=x1;
s[num].x2=x2;
s[num].h=y2;
s[num].d=-1;
line[num]=x2;
num++;
}
struct node2
{
int l,r,cover,m,line;
int lc,rc;
}tree[MAXN*3];
void creat(int rt,int l,int r)
{
tree[rt].cover=0;
tree[rt].line=0;
tree[rt].m=0;
tree[rt].l=l;
tree[rt].r=r;
if(l+1==r) return;
int mid=(l+r)>>1;
creat(rt<<1,l,mid);
creat(rt<<1|1,mid,r);
}
void up_m(int rt)
{
if(tree[rt].cover>0)
tree[rt].m=line[tree[rt].r]-line[tree[rt].l];
else if(tree[rt].l+1==tree[rt].r)
tree[rt].m=0;
else
tree[rt].m=tree[rt<<1].m+tree[rt<<1|1].m;
}
void up_line(int rt)
{
if(tree[rt].cover>0)
{
tree[rt].line=1;
tree[rt].lc=tree[rt].rc=1;
}
else if(tree[rt].l+1==tree[rt].r)
{
tree[rt].line=0;
tree[rt].lc=tree[rt].rc=0;
}
else
{
int left=rt<<1, right=left|1;
tree[rt].lc=tree[left].lc;
tree[rt].rc=tree[right].rc;
tree[rt].line=tree[left].line+tree[right].line - tree[left].rc*tree[right].lc;
}
}
void updata(int rt,int l,int r ,int d)
{
if(line[tree[rt].l]>=l && line[tree[rt].r]<=r)
tree[rt].cover+=d;
else if(tree[rt].l+1==tree[rt].r)
return;
else
{
int mid=(tree[rt].l+tree[rt].r)>>1;
if(line[mid]>=r) updata(rt<<1,l,r,d);
else if(line[mid]<=l) updata(rt<<1|1,l,r,d);
else
{
updata(rt<<1,l,line[mid],d);
updata(rt<<1|1,line[mid],r,d);
}
}
up_m(rt);
up_line(rt);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
num=0;
for(int i=0;i<n;i++) read_line();
sort(s,s+num);
sort(line,line+num);
int X=unique(line,line+num)-line;
creat(1,0,X-1);
int ans=0;
int now_m=0,now_line=0;
for(int i=0;i<num;i++)
{
updata(1,s[i].x1,s[i].x2,s[i].d);
if(i>0) ans+=2*now_line*(s[i].h-s[i-1].h);
ans+=abs(tree[1].m-now_m);
now_m=tree[1].m;
now_line=tree[1].line;
}
printf("%d\n",ans);
}
return 0;
}