北大pku poj 1177 picture 解题报告源代码
----北大pku acm 解题报告 源代码------
题目地址: [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1177[/url]
---------------------------------
[url]www.stubc.com[/url]
1.用一个struct记录所有矩形的纵向线段，用横坐标进行排序；同时对纵坐标进行离散化，存在一维数组a[]中，然后排序；具体见下面：
struct lines//记录纵向线段的结构体
{
int x,y1,y2;//线段横坐标和上下两个纵坐标
bool zuo;//如果是矩形的左边则为true，否则是false
void set(int xx,int yy1,int yy2,bool zzuo)//初始化用的函数
{
x=xx;
y1=yy1;
y2=yy2;
zuo=zzuo;
}
}l[2*S+1];
int a[2*S+!];//离散化纵向坐标用的数组
bool cmp(const lines &x,const lines &y)//线段排序用的函数
{
return x.x<y.x;
}
void init()//读入函数
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
l[2*i-1].set(x1,y1,y2,true);
l[2*i].set(x2,y1,y2,false);
a[2*i-1]=y1;
a[2*i]=y2;
}
sort(l+1,l+2*n+1,cmp);
sort(a+1,a+2*n+1);
}
[url]www.stubc.com[/url]
2.建树过程，线段树的定义稍后给出
root.build(1,2*n);
3.计算出解，这个过程请有兴趣的阅读者自己完成。我给出我写的线段树定义：
struct linestree
{
int i,j,count,m,line;//左端点、右端点、区间个数、测度、连续段数
bool lbj,rbj;//左端点是否被覆盖、右端点是否被覆盖
linestree *left,*right;//左儿子指针、右儿子指针
void build(int l,int r)//构建函数
{
int k;
i=l;
j=r;
count=line=m=lbj=rbj=0;
if (r-l>1)//如果不是元线段，即还有叶节点
{
k=(l+r)/2;
left=new linestree;
left->build(l,k);
right=new linestree;
right->build(k,r);
}
else left=right=NULL;
}
void update()//每次调用insert、del函数后更新测度、连续段数
{
if (count)
{
m=a[j]-a;
lbj=rbj=line=1;
}
else if (j-i==1) m=lbj=rbj=line=0;
else
{
m=left->m+right->m;
lbj=left->lbj;
rbj=right->rbj;
line=left->line+right->line-left->rbj*right->lbj;
}
}
void insert(int l,int r)//插入一个线段
{
if (l<=a && r>=a[j]) count++;
else
{
if (l<a[(i+j)/2]) left->insert(l,r);
if (r>a[(i+j)/2]) right->insert(l,r);
}
update();
}
void del(int l,int r)//删除一个线段
{
if (l<=a && r>=a[j])
{
if(l==a) lbj=0;
if(r==a[j]) rbj=0;
count--;
}
else
{
if (l<a[(i+j)/2]) left->del(l,r);
if (r>a[(i+j)/2]) right->del(l,r);
}
update();
}
}root;//根结点
[url]www.stubc.com[/url]