算是线段树的一个应用吧，在 hanyan 学长的帮助下，一天搞定了，略爽。
问题是，平面上有 n 个矩形，矩形的边是平行于 x 轴或 y 轴的，问它们覆盖的面积和周长。
大概思路是，用一根垂直于 x 轴的直线，从左向右扫描。扫描的过程中，一定会与某些矩形的边重合。
由于 n 个矩形会有 2*n 条竖边，所以我们可以把它们分成 2*n-1 个缝隙，我们依次考虑这些缝隙的情况，最后相加即可。
对于面积并，只需要知道 每个 缝隙 中在 y 轴方向各矩形所覆盖的区间长度，再乘以缝隙的宽，就是这个缝隙内所覆盖的面积。
对于周长并，则需要知道区间内有几个连续子区间被覆盖，个数*2 即是它们出现在周长中的边数，再 * 缝隙的宽，就是 x 方向的周长。
y 方向的周长则是在扫描的过程中，每相邻两次在 y 轴方向各矩形所覆盖的区间长度差。
面积并，例题。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e2+5;
#define lson u<<1
#define rson u<<1|1
struct Seg
{
double x,y1,y2;
bool pos;
Seg(){}
Seg(double x,double y1,double y2,int i):x(x),y1(y1),y2(y2),pos(i&1){}
bool operator < (const Seg& S) const{
return x < S.x;
}
}s[N<<1];
double y[N<<1];
bool del;
struct SegTree
{
int l,r,cover_cnt;
double cover_len;
inline int mid(){
return l+r >> 1;
}
inline double len(){
return y[r] - y[l];
}
}T[N<<3];
void get_len(int u)
{
if(T[u].cover_cnt > 0)
T[u].cover_len = T[u].len();
else
if(T[u].l == T[u].r-1)
T[u].cover_len = 0.0;
else
T[u].cover_len = T[lson].cover_len + T[rson].cover_len;
}
void build(int u,int l,int r)
{
T[u].l = l , T[u].r = r;
T[u].cover_len = T[u].cover_cnt = 0;
int m = T[u].mid();
if(l != r-1)
build(lson,l,m) , build(rson,m,r);
}
void updata(int u,double l,double r)
{
if(l == y[T[u].l] && r == y[T[u].r])
{
T[u].cover_cnt += del ? -1 : 1;
get_len(u);
return ;
}
int m = T[u].mid();
if(r <= y[m])
updata(lson,l,r);
else if(l >= y[m])
updata(rson,l,r);
else
updata(lson,l,y[m]) , updata(rson,y[m],r);
get_len(u);
}
double solve(int n)
{
double res = 0;
del = s[0].pos;
updata(1,s[0].y1,s[0].y2);
for(int i=1;i<n;i++)
{
res += (s[i].x-s[i-1].x) * T[1].cover_len;
del = s[i].pos;
updata(1,s[i].y1,s[i].y2);
}
return res;
}
int main()
{
int n,ncase = 0;
while(scanf("%d",&n),n)
{
n *= 2;
for(int i=0;i<n;i+=2)
{
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
s[i] = Seg(x1,y1,y2,i) , s[i+1] = Seg(x2,y1,y2,i+1);
y[i] = y1 , y[i+1] = y2;
}
sort(y,y+n);
int nn = unique(y,y+n) - y;
build(1,0,nn-1);
sort(s,s+n);
printf("Test case #%d\n",++ncase);
printf("Total explored area: %.2f\n",solve(n));
puts("");
}
return 0;
}
周长并，例题。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 5e3+5;
#define lson u<<1
#define rson u<<1|1
struct Seg
{
int x,y1,y2;
bool pos;
Seg(){}
Seg(int x,int y1,int y2,int i):x(x),y1(y1),y2(y2),pos(i&1){}
bool operator < (const Seg& S) const{
return x < S.x;
}
}s[N<<1];
int y[N<<1];
bool del;
struct SegTree
{
int l,r,cover_cnt,cover_len,interval_cnt;
bool cover_l,cover_r;
inline int mid(){
return l+r >> 1;
}
inline int len(){
return y[r] - y[l];
}
}T[N<<3];
void get_len(int u)
{
if(T[u].cover_cnt > 0)
T[u].cover_len = T[u].len();
else
if(T[u].l == T[u].r-1)
T[u].cover_len = 0.0;
else
T[u].cover_len = T[lson].cover_len + T[rson].cover_len;
}
void get_cnt(int u)
{
if(T[u].cover_cnt > 0)
{
T[u].interval_cnt = 1;
T[u].cover_l = T[u].cover_r = true;
}
else
if(T[u].l == T[u].r-1)
{
T[u].interval_cnt = 0;
T[u].cover_l = T[u].cover_r = false;
}
else
{
T[u].interval_cnt = T[lson].interval_cnt + T[rson].interval_cnt;
if(T[lson].cover_r && T[rson].cover_l)
T[u].interval_cnt --;
T[u].cover_l = T[lson].cover_l;
T[u].cover_r = T[rson].cover_r;
}
}
void build(int u,int l,int r)
{
T[u].l = l , T[u].r = r;
T[u].cover_len = T[u].cover_cnt = T[u].interval_cnt = 0;
T[u].cover_l = T[u].cover_r = false;
int m = T[u].mid();
if(l != r-1)
build(lson,l,m) , build(rson,m,r);
}
void updata(int u,int l,int r)
{
if(l == y[T[u].l] && r == y[T[u].r])
{
T[u].cover_cnt += del ? -1 : 1;
get_len(u);
get_cnt(u);
return ;
}
int m = T[u].mid();
if(r <= y[m])
updata(lson,l,r);
else if(l >= y[m])
updata(rson,l,r);
else
updata(lson,l,y[m]) , updata(rson,y[m],r);
get_len(u);
get_cnt(u);
}
int solve(int n)
{
int res = 0 , last_depth = 0;
del = s[0].pos;
updata(1,s[0].y1,s[0].y2);
res += T[1].cover_len;
for(int i=1;i<n;i++)
{
res += (s[i].x-s[i-1].x) * T[1].interval_cnt*2;
del = s[i].pos;
last_depth = T[1].cover_len;
updata(1,s[i].y1,s[i].y2);
res += abs(T[1].cover_len - last_depth);
}
return res;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
n *= 2;
for(int i=0;i<n;i+=2)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
s[i] = Seg(x1,y1,y2,i) , s[i+1] = Seg(x2,y1,y2,i+1);
y[i] = y1 , y[i+1] = y2;
}
sort(y,y+n);
int nn = unique(y,y+n) - y;
build(1,0,nn-1);
sort(s,s+n);
printf("%d\n",solve(n));
}
return 0;
}