首页 > 代码库 > TreeSegment1177
TreeSegment1177
题意：求多个矩形周长覆盖问题
//POJ 1177
//N个矩形求总周长
//线段树+离散化+扫描线
//2010年7月21日19:35:45
//Coded By abilitytao
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10010
struct STnode //线段树的节点
{
int l,r;
int len;//区间内代表的长度
int segnum;//区间内被分成的段数
int cover;//区间被覆盖的次数
int sum;//区间中被覆盖的总长度
bool lcover,rcover;//标记左右端点是否被覆盖，用于合并区间时候统计区间内的离散线段数
STnode()//初始化
{
l = r = 0;
len = segnum = cover = sum = 0;
lcover = rcover = false;
}
};
STnode ST[MAXN*4];//整棵线段树
struct Line
{
int st,ed;//竖边的两个y值
int x;//此条边的x值
bool InOut;//是否为入边
bool operator<(Line o) const//重载小于符号
{
return x<o.x;
}
};
Line Yline[MAXN];//存储竖边
int Index[MAXN];//存储离散后的y值
int cnt=0;
int n;//存储矩形的数目
void Build(int l,int r,int i)//创建线段树
{//线段树必须连续,[l,r]连续
ST[i].l=l;
ST[i].r=r;
ST[i].cover=0;
ST[i].len=Index[r]-Index[l];
ST[i].segnum=0;
ST[i].sum=0;
ST[i].lcover=ST[i].rcover=false;
//建立线段的时候进行初始化
if(r-l>1)
{
int mid=(l+r)>>1;
Build(l,mid,i*2);
Build(mid,r,i*2+1);
}
}
void GetLen(int i)//求该线段树节点已经覆盖的线段长度
{
if(ST[i].cover>0)
ST[i].sum=ST[i].len;
else if(ST[i].r-ST[i].l>1)
ST[i].sum=ST[i*2].sum+ST[i*2+1].sum;
else//叶节点下面没有子节点，强制设置为0
ST[i].sum=0;
}
void GetSegNum(int i)//求该区间所包含的线段数总量（就是含有不想交的线段的条数）
{
if(ST[i].cover>0)
{
ST[i].lcover=ST[i].rcover=true;//完全覆盖
ST[i].segnum=1;//一条线段就可以完整覆盖该区域
}
else if(ST[i].r-ST[i].l>1)
{//不能完全覆盖，左节点（最小值）覆盖情况即是左子节点的左节点覆盖情况.
ST[i].lcover=ST[i*2].lcover;
ST[i].rcover=ST[i*2+1].rcover;//该区域被多少条线段覆盖的数量是两个孩子的覆盖数量，另外还要考虑左孩子右边是否与右孩子左边相连，如
ST[i].segnum=ST[i*2].segnum+ST[i*2+1].segnum-ST[i*2].rcover*ST[i*2+1].lcover;//【1,2】【2,3】如果两个2都被覆盖，说明多算了一条（这里把所有连续的线段都看做是一条）
}
else
{
ST[i].lcover=ST[i].rcover=false;//叶节点下面没有子节点，强制设置为0
ST[i].segnum=0;
}
}
void Insert(int l,int r,int i)//插入一条线段
{
if(ST[i].l==l&&ST[i].r==r)
ST[i].cover++;
else
{
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
Insert(l,r,i*2);
else if(l>=mid)
Insert(l,r,i*2+1);
else
{
Insert(l,mid,i*2);
Insert(mid,r,i*2+1);
}
}
GetLen(i);
GetSegNum(i);
}
void Delete(int l,int r,int i)//删除矩形的右边
{
if(ST[i].l==l&&ST[i].r==r)
ST[i].cover--;
else
{
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
Delete(l,r,i*2);
else if(l>=mid)
Delete(l,r,i*2+1);
else
{
Delete(l,mid,i*2);
Delete(mid,r,i*2+1);
}
}
GetLen(i);
GetSegNum(i);
//这个后序操作非常精彩！
}
int GetIndex(int x)// 返回index中数值为x的下标
{
return lower_bound(Index,Index + cnt,x) - Index;//lower_bound函数返回一个元素在容器中的迭代器，数组index可以看成特殊的容器，所以这里返回的迭代器就是指针
//针对的是index数组
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
cnt=0;
int i,j,k;
int x1,x2,y1,y2;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Yline[i*2].x=x1;
Yline[i*2+1].x=x2;
Yline[2*i].st=Yline[2*i+1].st=y1;
Yline[2*i].ed=Yline[2*i+1].ed=y2;
Yline[2*i].InOut=true;//标记入边
Yline[2*i+1].InOut=false;
Index[2*i]=y1;
Index[2*i+1]=y2;
}
sort(Index,Index+n*2);
sort(Yline,Yline+n*2);
for(int i=1;i<n*2;i++)//Y数组去重
{
if(Index[i]!=Index[i-1])
Index[cnt++]=Index[i-1];
}
Index[cnt++]=Index[2*n-1];//这里很容易错!
/*去重操作以后，水平方向就只有cnt种坐标了，以cnt建立线段树。消除重复的目的在于防止出现[1,2] [3,4]两条线段，而实际上，第2和第3是同一个坐标，因此一条连续线段被当做一条线段
*/
Build(0,cnt-1,1);
int Ans=0;
int Lsum=0;//上一次记录的长度，画个图很好理解
for(int i=0;i<2*n-1;i++)
{
if(Yline[i].InOut)
Insert(GetIndex(Yline[i].st),GetIndex(Yline[i].ed),1);//GetIndex(Yline[i].ed)得到离散后的值，带入线段树，线段树里放的都是离散后的
else
Delete(GetIndex(Yline[i].st),GetIndex(Yline[i].ed),1);
/*计算水平方向边的周长，如果根节点统计的段数只有一个，说明水平方向只有一个连续边，那么垂直方向要计算两次即可。如果是
水平方向有两个不连续的边，那么统计垂直方向边的周长时候，就要计算四次一次类推*/
Ans+=ST[1].segnum*(Yline[i+1].x-Yline[i].x)*2;
Ans+=abs(ST[1].sum-Lsum);//加上水平方向的边长。求的时候要用目前所有线段的累积长度（重叠部分算一次）减去前一次的累积长度
Lsum=ST[1].sum;
}
//特殊处理最后一条出边，因为没有下一条竖边了
Delete(GetIndex(Yline[2*n-1].st),GetIndex(Yline[2*n-1].ed),1);
Ans+=abs(ST[1].sum-Lsum);
//也可以这么做： int a=GetIndex(Yline[2*n-1].st);
// int b=GetIndex(Yline[2*n-1].ed);
// Ans+=Index[b]-Index[a];
// printf("%d\n",Ans);
}
return 0;
}
TreeSegment1177